ขอบเขตของไบนารีทรีใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาค่าขอบเขตของมันในทิศทางทวนเข็มนาฬิกาโดยเริ่มจากรูท ขอบเขตนี้รวมถึงขอบด้านซ้าย ใบไม้ และขอบด้านขวาตามลำดับโดยไม่มีโหนดที่ซ้ำกัน

• ขอบด้านซ้ายคือเส้นทางจากรูทไปยังโหนดด้านซ้ายสุด

• ขอบเขตด้านขวาคือเส้นทางจากรูทไปยังโหนดขวาสุด

• เมื่อรูทไม่มีทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวา รูทเองจะเป็นขอบด้านซ้ายหรือขอบด้านขวา

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น [1,2,4,7,8,9,10,6,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ ret

• กำหนดฟังก์ชัน leftBoundary() ซึ่งจะใช้โหนด

• ถ้าโหนดเป็นโมฆะหรือโหนดเป็นลีฟ −

  • กลับ

• แทรกค่าของโหนดใน ret

• ถ้าโหนดเหลืออยู่ −

  • leftBoundary(ซ้ายของโหนด)

• มิฉะนั้น

  • leftBoundary(ทางขวาของโหนด)

• กำหนดฟังก์ชัน rightBoundary() ซึ่งจะรับโหนด

• ถ้าโหนดเป็นโมฆะหรือโหนดเป็นลีฟ −

  • กลับ

• แทรกค่าของโหนดใน ret

• หากมีสิทธิ์ของโหนด −

  • rightBoundary(ซ้ายของโหนด)

• มิฉะนั้น

  • rightBoundary(ขวาของโหนด)

• กำหนดฟังก์ชัน Leave() ซึ่งจะใช้โหนด

• หากไม่มีโหนด ดังนั้น −

  • กลับ

• ถ้าโหนดเป็นลีฟ −

  • แทรก val ของโหนดใน ret

• ใบไม้ (ด้านซ้ายของโหนด)

• ใบไม้ (ทางขวาของโหนด)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ล้างอาร์เรย์ ret

• หากไม่มีรูทอยู่ −

  • รีเทิร์น

• แทรก val ของ root ลงใน ret

• leftBoundary(ซ้ายของรูท)

• ใบไม้ (ด้านซ้ายของราก);

• ใบไม้(ทางขวาของรูท);

• rightBoundary(ทางขวาของรูท)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   vector<int> ret;
   void leftBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      ret.push_back(node->val);
      if (node->left && node->left->val != 0)
         leftBoundary(node->left);
      else
         leftBoundary(node->right);
   }
   void rightBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      if (node->right && node->right->val != 0) {
         rightBoundary(node->right);
      }
      else {
         rightBoundary(node->left);
      }
      ret.push_back(node->val);
   }
   void leaves(TreeNode* node){
      if (!node || node->val == 0)
         return;
      if (!node->left && !node->right) {
         ret.push_back(node->val);
      }
      leaves(node->left);
      leaves(node->right);
   }
   vector<int> boundaryOfBinaryTree(TreeNode* root){
      ret.clear();
      if (!root)
         return ret;
      ret.push_back(root->val);
      leftBoundary(root->left);
      leaves(root->left);
      leaves(root->right);
      rightBoundary(root->right);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
   TreeNode *root = make_tree(v);
   print_vector(ob.boundaryOfBinaryTree(root));
}

อินพุต

{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}

ผลลัพธ์

[1, 2, 4, 7, 8, 9, 10, 6, 3, ]