ค้นหาองค์ประกอบในทรีไบนารีที่ปนเปื้อนใน C++

สมมติว่าเรามีต้นไม้ไบนารี กฎของต้นไม้ต้นนั้นมีดังนี้ −

• root.val ==0

• หาก treeNode.val เป็น x และ treeNode.left ไม่เป็นค่าว่าง ดังนั้น treeNode.left.val =2 * x + 1

• หาก treeNode.val คือ x และ treeNode.right ไม่เป็นค่าว่าง ดังนั้น treeNode.right.val =2 * x + 2

ตอนนี้เนื่องจากไบนารีทรีถูกปนเปื้อน สิ่งนี้บ่งชี้ว่า val ของโหนดทรีทั้งหมดถูกเปลี่ยนเป็น -1 เราต้องกู้คืนไบนารีทรีก่อนแล้วจึงใช้คลาส FindElements ดังนี้ -

• FindElements(TreeNode* root) เริ่มต้นวัตถุด้วยไบนารีทรีที่ปนเปื้อน เราต้องกู้คืนก่อน

• ค้นหาบูล (int เป้าหมาย) สิ่งนี้จะคืนค่าหากมีค่าเป้าหมายอยู่ในทรีไบนารีที่กู้คืน

ดังนั้นถ้าต้นไม้เป็นเหมือน −

ดังนั้นหลังจากหายดีแล้ว หากเราพยายามหา 1, 3 และ 5 ผลลัพธ์จะเป็นจริง จริง และเท็จ

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

• กำหนดชุด

• กำหนดวิธีการ dfs() ซึ่งจะทำการรูทและ rootVal rootVal คือ -1

• หากรูทเป็นโมฆะ ให้ส่งคืน

• ถ้า rootVal เป็น -1 ให้ตั้งค่าของ root เป็น 0 มิฉะนั้น ให้ตั้งค่าเป็น rootVal

• แทรกค่าของ root ลงใน a

• โทร dfs (ด้านซ้ายของรูท, ค่ารูท 2* ค่า + 1), dfs (ทางขวาของรูท, ค่ารูท 2* ค่า + 2)

• สำหรับการเริ่มต้น (หรือการสร้างใหม่) เราจะเรียก dfs(root, -1)

• หากต้องการค้นหาองค์ประกอบบางรายการ ให้ตรวจสอบว่าองค์ประกอบนั้นอยู่ใน a หรือไม่ หาก return เป็น true หรือเป็นเท็จ

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
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 FindElements {
   public:
   set <int> a;
   void dfs(TreeNode* root,int rootVal=-1){
      if(!root)return;
      root->val = rootVal == -1?0:rootVal;
      a.insert(root->val);
      dfs(root->left,2*root->val + 1);
      dfs(root->right, 2*root->val + 2);
   }
   FindElements(TreeNode* root) {
      dfs(root);
   }
   bool find(int t) {
      return a.find(t)!=a.end();
   }
};
main(){
   vector<int> v = {-1,-1,-1,-1,-1};
   TreeNode *root = make_tree(v);
   FindElements ob(root);
   cout << (ob.find(1)) << endl;
   cout << (ob.find(3)) << endl;
   cout << (ob.find(5)) << endl;
}

อินพุต

Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)

ผลลัพธ์

1
1
0