与えられた二分木の垂直レベルがC++でソートされているかどうかを調べます

コンセプト

特定の二分木に関して、私たちのタスクは、二分木の特定の垂直レベルがソートされているかどうかを判断することです。

（この場合、2つのノードがオーバーラップしているときは、それらが存在するレベルでソートされたシーケンスを形成しているかどうかを確認してください。）

入力

2
/ \
3 6
/ \
8 5
  /
7
Level l = -1

出力

Yes

レベル-1のノードは3->7であり、ソートされたシーケンスを形成します。

入力

2
/ \
3 7
\ /
4 5
Level l = 0

出力

Yes

値4と5のノードがバイナリツリーで重複していることに注意してください。

ここで、これがソートされたシーケンスレベルで形成されるかどうかを確認します。レベル0のノードは2->4->5であり、ソートされたシーケンスを形成します。

メソッド

簡単な解決策によれば、最初にバイナリツリーのレベル順序トラバーサルを実行し、各垂直レベルを異なる配列に格納します。この場合、レベルlに対応する配列がソートされているかどうかを確認します。このソリューションには、削減できる大きなメモリ要件があることに注意してください。

効率的な解決策に従って、バイナリツリーの垂直レベルの順序トラバーサルを実行し、バイナリツリーの垂直レベルlのノード値の追跡を維持します。前の要素が現在の要素以下の場合、ソートされたシーケンスが生成されます。垂直レベルの順序トラバーサルを実行するときに、以前の値を保存し、垂直レベルlの現在のノードをレベルlのこの以前の値と比較します。現在のノード値が前の値以上の場合、レベルlが終了するまで同じ手順を繰り返す必要があることがわかっています。いずれかの段階で現在のノード値が前の値よりも小さい場合、レベルlはソートされないことがわかりました。ここでも、レベルlの終わりに到達すると、レベルが並べ替えられることが確認されています。

例

// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Shows structure of a tree node.
struct Node1 {
   int key1;
   Node1 *left1, *right1;
};
// Shows function to create new tree node.
Node1* newNode(int key1){
   Node1* temp1 = new Node1;
   temp1->key1 = key1;
   temp1->left1 = temp1->right1 = NULL;
   return temp1;
}
// Indicates helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted1(Node1* root1, int level1){
   // So If root is null, then the answer is an
   // empty subset and an empty subset is
   // always considered to be sorted.
   if (root1 == NULL)
      return true;
   // Indicates variable to store previous
   // value in vertical level l.
   int prevVal1 = INT_MIN;
   // Indicates variable to store current level
   // while traversing tree vertically.
   int currLevel1;
   // Indicates variable to store current node
   // while traversing tree vertically.
   Node1* currNode1;
   // Used to 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<Node1*, int>> q1;
   // Used to insert root in queue. Vertical level
   // of root is 0.
   q1.push(make_pair(root1, 0));
   // Perform vertical order traversal until
   // all the nodes are not visited.
   while (!q1.empty()) {
      currNode1 = q1.front().first;
      currLevel1 = q1.front().second;
      q1.pop();
      // Verify if level of node extracted from
      // queue is required level or not. If it
      // is the required level then verify if
      // previous value in that level is less
      // than or equal to value of node.
      if (currLevel1 == level1) {
         if (prevVal1 <= currNode1->key1)
            prevVal1 = currNode1->key1;
      else
         return false;
   }
   // So if left child is not NULL then push it
   // in queue with level reduced by 1.
   if (currNode1->left1)
      q1.push(make_pair(currNode1->left1, currLevel1 - 1));
   // So if right child is not NULL then push it
   // in queue with level increased by 1.
   if (currNode1->right1)
      q1.push(make_pair(currNode1->right1, currLevel1 + 1));
   }
   // So 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(){
/*
      2
      / \
      3 6
      / \
      8 5
        /
      7
*/
   Node1* root1 = newNode(2);
   root1->left1 = newNode(3);
   root1->right1 = newNode(6);
   root1->left1->left1 = newNode(8);
   root1->left1->right1 = newNode(5);
   root1->left1->right1->left1 = newNode(7);
   int level1 = -1;
   if (isSorted1(root1, level1) == true)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

出力

Yes