Проверьте, отсортировано ли двоичное дерево по уровням или нет

Опубликовано: 24 Января, 2022

Дано двоичное дерево. Задача - проверить, отсортировано ли бинарное дерево по уровням или нет. Двоичное дерево сортируется по уровням, если 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 
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022