Проверьте, отсортировано ли двоичное дерево по уровням или нет
Дано двоичное дерево. Задача - проверить, отсортировано ли бинарное дерево по уровням или нет. Двоичное дерево сортируется по уровням, если max (i-1- й уровень) меньше min (i- й уровень).
Примеры :
Ввод: 1 / / 2 3 / / / / 4 5 6 7 Вывод: отсортировано Ввод: 1 / 4 / 6 5 2 Вывод: не отсортировано
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Простое решение : простое решение - сравнить минимальное и максимальное значение каждого соседнего уровня i и i + 1. Перейти на i- й и i + 1- й уровень, сравнить минимальное значение i + 1- го уровня с максимальным значением i- го уровня и вернуть результат.
Временная сложность: O (n 2 ).
Эффективное решение . Эффективным решением является обход порядка уровней и отслеживание минимальных и максимальных значений текущего уровня. Используйте переменную prevMax, чтобы сохранить максимальное значение предыдущего уровня. Затем сравните минимальное значение текущего уровня с максимальным значением предыдущего уровня pevMax . Если минимальное значение больше, чем prevMax , то данное дерево сортируется по уровням до текущего уровня. Для следующего уровня prevMax равно максимальному значению текущего уровня. Поэтому обновите prevMax с максимальным значением текущего уровня. Повторяйте это, пока не пройдете все уровни данного дерева.
Below is the implementation of above approach:
C++
// CPP program to determine whether // binary tree is level sorted or not. #include <bits/stdc++.h> using namespace std; // Structure of a tree node. struct Node { int key; Node *left, *right; }; // Function to create new tree node. Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } // Function to determine if // given binary tree is level sorted // or not. int isSorted(Node* root) { // to store maximum value of previous // level. int prevMax = INT_MIN; // to store minimum value of current // level. int minval; // to store maximum value of current // level. int maxval; // to store number of nodes in current // level. int levelSize; // queue to perform level order traversal. queue<Node*> q; q.push(root); while (!q.empty()) { // find number of nodes in current // level. levelSize = q.size(); minval = INT_MAX; maxval = INT_MIN; // traverse current level and find // minimum and maximum value of // this level. while (levelSize > 0) { root = q.front(); q.pop(); levelSize--; minval = min(minval, root->key); maxval = max(maxval, root->key); if (root->left) q.push(root->left); if (root->right) q.push(root->right); } // if minimum value of this level // is not greater than maximum // value of previous level then // given tree is not level sorted. if (minval <= prevMax) return 0; // maximum value of this level is // previous maximum value for // next level. prevMax = maxval; } return 1; } // Driver program int main() { /* 1 / 4
6 / 8 9 / 12 10 */ Node* root = newNode(1); root->left = newNode(4); root->left->right = newNode(6); root->left->right->left = newNode(8); root->left->right->right = newNode(9); root->left->right->left->left = newNode(12); root->left->right->right->right = newNode(10); if (isSorted(root)) cout << "Sorted" ; else cout << "Not sorted" ; return 0; } |
Java
// Java program to determine whether // binary tree is level sorted or not. import java.util.*; class GfG { // Structure of a tree node. static class Node { int key; Node left, right; } // Function to create new tree node. static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = null ; temp.right = null ; return temp; } // Function to determine if // given binary tree is level sorted // or not. static int isSorted(Node root) { // to store maximum value of previous // level. int prevMax = Integer.MIN_VALUE; // to store minimum value of current // level. int minval; // to store maximum value of current // level. int maxval; // to store number of nodes in current // level. int levelSize; // queue to perform level order traversal. Queue<Node> q = new LinkedList<Node> (); q.add(root); while (!q.isEmpty()) { // find number of nodes in current // level. levelSize = q.size(); minval = Integer.MAX_VALUE; maxval = Integer.MIN_VALUE; // traverse current level and find // minimum and maximum value of // this level. while (levelSize > 0 ) { root = q.peek(); q.remove(); levelSize--; minval = Math.min(minval, root.key); maxval = Math.max(maxval, root.key); if (root.left != null ) q.add(root.left); if (root.right != null ) q.add(root.right); } // if minimum value of this level // is not greater than maximum // value of previous level then // given tree is not level sorted. if (minval <= prevMax) return 0 ; // maximum value of this level is // previous maximum value for // next level. prevMax = maxval; } return 1 ; } // Driver program public static void main(String[] args) { /* 1 / 4 6 / 8 9 / 12 10 */ Node root = newNode( 1 ); root.left = newNode( 4 ); root.left.right = newNode( 6 ); root.left.right.left = newNode( 8 ); root.left.right.right = newNode( 9 ); root.left.right.left.left = newNode( 12 ); root.left.right.right.right = newNode( 10 ); if (isSorted(root) == 1 ) System.out.println( "Sorted" ); else System.out.println( "Not sorted" ); } } |
Python3
# Python3 program to determine whether # binary tree is level sorted or not. from queue import Queue # Function to create new tree node. class newNode: def __init__( self , key): self .key = key self .left = self .right = None # Function to determine if given binary # tree is level sorted or not. def isSorted(root): # to store maximum value of previous # level. prevMax = - 999999999999 # to store minimum value of current # level. minval = None # to store maximum value of current # level. maxval = None # to store number of nodes in current # level. levelSize = None # queue to perform level order traversal. q = Queue() q.put(root) while ( not q.empty()): # find number of nodes in current # level. levelSize = q.qsize() minval = 999999999999 maxval = - 999999999999 # traverse current level and find # minimum and maximum value of # this level. while (levelSize > 0 ): root = q.queue[ 0 ] q.get() levelSize - = 1 minval = min (minval, root.key) maxval = max (maxval, root.key) if (root.left): q.put(root.left) if (root.right): q.put(root.right) # if minimum value of this level # is not greater than maximum # value of previous level then # given tree is not level sorted. if (minval < = prevMax): return 0 # maximum value of this level is # previous maximum value for # next level. prevMax = maxval return 1 # Driver Code if __name__ = = "__main__" : # # 1 # / # 4 # # 6 # / # 8 9 # / # 12 10 root = newNode( 1 ) root.left = newNode( 4 ) root.left.right = newNode( 6 ) root.left.right.left = newNode( 8 ) root.left.right.right = newNode( 9 ) root.left.right.left.left = newNode( 12 ) root.left.right.right.right = newNode( 10 ) if (isSorted(root)): print ( "Sorted" ) else : print ( "Not sorted" ) # This code is contributed by PranchalK |
C#
// C# program to determine whether // binary tree is level sorted or not. using System; using System.Collections.Generic; class GFG { // Structure of a tree node. public class Node { public int key; public Node left, right; } // Function to create new tree node. static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = null ; temp.right = null ; return temp; } // Function to determine if // given binary tree is level sorted // or not. static int isSorted(Node root) { // to store maximum value of previous // level. int prevMax = int .MinValue; // to store minimum value of current // level. int minval; // to store maximum value of current // level. int maxval; // to store number of nodes in current РЕКОМЕНДУЕМЫЕ СТАТЬИ |