ค้นหาว่ามีการเรียงลำดับต้นไม้ไบนารีในระดับแนวตั้งหรือไม่ใน C ++

แนวคิด

ในส่วนที่เกี่ยวกับไบนารีทรีที่กำหนด หน้าที่ของเราคือตรวจสอบว่าระดับแนวตั้งที่กำหนดของไบนารีทรีนั้นได้รับการจัดเรียงหรือไม่

(สำหรับกรณีนี้ เมื่อโหนดสองโหนดซ้อนทับกัน ให้ตรวจสอบว่าโหนดเหล่านี้จัดลำดับในระดับที่โหนดอยู่หรือไม่)

อินพุต

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