Найти, отсортирован ли данный вертикальный уровень двоичного дерева или нет

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

Дано двоичное дерево. Узнайте, отсортирован ли данный вертикальный уровень двоичного дерева.
(В случае, когда два узла перекрываются, проверьте, образуют ли они отсортированную последовательность на том уровне, на котором они лежат.)

Предпосылка: вертикальный обход заказа

Примеры:

Ввод: 1
       / 
      2 5
     / 
    7 4
       /
      6
   Уровень l = -1   
Выход: Да
Узлы на уровне -1: 2 -> 6, которые
образует отсортированную последовательность.

Ввод: 1
        / 
       2 6
         /
        3 4
   Уровень l = 0
Выход: Да
Обратите внимание, что узлы со значениями 3 и 4
перекрываются в двоичном дереве.
Итак, мы проверяем, является ли эта форма отсортированной
на уровне последовательности. Последовательность сформирована
на уровне 0 это 1 -> 3 -> 4, который отсортирован.

Рекомендуется: сначала попробуйте свой подход в среде IDE, а затем посмотрите решение.

Простое решение - сначала выполнить обход двоичного дерева в порядке уровней и сохранить каждый вертикальный уровень в разных массивах. После этого проверьте, отсортирован ли массив, соответствующий уровню l. Это решение требует больших объемов памяти, которые можно уменьшить.

Эффективное решение состоит в том, чтобы выполнять обход двоичного дерева в порядке вертикального уровня и отслеживать значения узлов на вертикальном уровне l двоичного дерева. Последовательность сортируется, если предыдущий элемент меньше или равен текущему элементу. При выполнении обхода порядка вертикального уровня сохраните предыдущее значение и сравните текущий узел на вертикальном уровне l с этим предыдущим значением уровня l. Если текущее значение узла больше или равно предыдущему значению, повторите ту же процедуру до конца уровня l. Если на каком-либо этапе текущее значение узла меньше предыдущего значения, то уровень l не сортируется. Если мы дойдем до конца уровня l, то уровень будет отсортирован.

Implementation:

C++

// CPP program to determine whether
// vertical level l of binary tree
// is 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;
}
  
// Helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted(Node* root, int level)
{
    // If root is null, then the answer is an
    // empty subset and an empty subset is
    // always considered to be sorted.
    if (root == NULL) 
        return true;
      
    // Variable to store previous
    // value in vertical level l.
    int prevVal = INT_MIN;
  
    // Variable to store current level
    // while traversing tree vertically.
    int currLevel;
  
    // Variable to store current node
    // while traversing tree vertically.
    Node* currNode;
  
    // Declare queue to do vertical order
    // traversal. A pair is used as element
    // of queue. The first element in pair
    // represents the node and the second
    // element represents vertical level
    // of that node.
    queue<pair<Node*, int> > q;
  
    // Insert root in queue. Vertical level
    // of root is 0.
    q.push(make_pair(root, 0));
  
    // Do vertical order traversal until
    // all the nodes are not visited.
    while (!q.empty()) {
        currNode = q.front().first;
        currLevel = q.front().second;
        q.pop();
  
        // Check if level of node extracted from
        // queue is required level or not. If it
        // is the required level then check if
        // previous value in that level is less
        // than or equal to value of node.
        if (currLevel == level) {
            if (prevVal <= currNode->key) 
                prevVal = currNode->key;            
            else 
                return false;            
        }
  
        // If left child is not NULL then push it
        // in queue with level reduced by 1.
        if (currNode->left)
            q.push(make_pair(currNode->left, currLevel - 1));
  
        // If right child is not NULL then push it
        // in queue with level increased by 1.
        if (currNode->right)
            q.push(make_pair(currNode->right, currLevel + 1));
    }
  
    // If the level asked is not present in the
    // given binary tree, that means that level
    // will contain an empty subset. Therefore answer
    // will be true.
    return true;
}
  
// Driver program
int main()
{
    /*
             1
            / 
           2   5
          / 
         7   4
            /
           6
    */
  
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(7);
    root->left->right = newNode(4);
    root->left->right->left = newNode(6);
  
    int level = -1;
    if (isSorted(root, level) == true)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Python3

# Python program to determine whether
# vertical level l of binary tree
# is sorted or not.
from collections import deque
from sys import maxsize
  
INT_MIN = -maxsize
  
# Structure of a tree node.
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
  
# Helper function to determine if
# vertical level l of given binary
# tree is sorted or not.
def isSorted(root: Node, level: int) -> bool:
  
    # If root is null, then the answer is an
    # empty subset and an empty subset is
    # always considered to be sorted.
    if root is None:
        return True
  
    # Variable to store previous
    # value in vertical level l.
    prevVal = INT_MIN
  
    # Variable to store current level
    # while traversing tree vertically.
    currLevel = 0
  
    # Variable to store current node
    # while traversing tree vertically.
    currNode = Node(0)
  
    # Declare queue to do vertical order
    # traversal. A pair is used as element
    # of queue. The first element in pair
    # represents the node and the second
    # element represents vertical level
    # of that node.
    q = deque()
  
    # Insert root in queue. Vertical level
    # of root is 0.
    q.append((root, 0))
  
    # Do vertical order traversal until
    # all the nodes are not visited.
    while q:
        currNode = q[0][0]
        currLevel = q[0][1]
        q.popleft()
  
        # Check if level of node extracted from
        # queue is required level or not. If it
        # is the required level then check if
        # previous value in that level is less
        # than or equal to value of node.
        if currLevel == level:
            if prevVal <= currNode.key:
                prevVal = currNode.key
            else:
                return False
  
        # If left child is not NULL then push it
        # in queue with level reduced by 1.
        if currNode.left:
            q.append((currNode.left, currLevel - 1))
  
        # If right child is not NULL then push it
        # in queue with level increased by 1.
        if currNode.right:
            q.append((currNode.right, currLevel + 1))
  
    # If the level asked is not present in the
    # given binary tree, that means that level
    # will contain an empty subset. Therefore answer
    # will be true.
    return True
  
# Driver Code
if __name__ == "__main__":
  
    # /*
    #         1
    #         / 
    #     2 5
    #     / 
    #     7 4
    #         /
    #     6
    # */
  
    root = Node(1)
    root.left = Node(2)
    root.right = Node(5)
    root.left.left = Node(7)
    root.left.right = Node(4)
    root.left.right.left = Node(6)
  
    level = -1
    if isSorted(root, level):
        print("Yes")
    else:
        print("No")
  
# This code is contributed by
# sanjeev2552

Output:

Yes

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Найти, отсортирован ли данный вертикальный уровень двоичного дерева или нет

C++

Python3

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