ต้นไม้เดียวกันใน C++

สมมติว่าเรามีต้นไม้ไบนารีสองต้น เราต้องกำหนดฟังก์ชั่นเพื่อตรวจสอบว่าเหมือนกันหรือไม่ เรารู้ว่าไบนารีทรีจะถือว่าเหมือนกันเมื่อมีโครงสร้างเหมือนกันและโหนดมีค่าเท่ากัน

ดังนั้น หากอินพุตเป็น [1,2,3],[1,2,3] ผลลัพธ์จะเป็น True

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

• กำหนดฟังก์ชันที่เรียกว่า isSameTree ซึ่งจะใช้โหนดทรีสองโหนด p และ q

• ถ้า p เท่ากับ NULL และ q เหมือนกับ NULL ดังนั้น −

  • คืนความจริง

• ถ้า p เท่ากับ NULL หรือ q เหมือนกับ NULL ดังนั้น −

  • คืนค่าเท็จ

• ถ้า val ของ p เหมือนกับ val ของ p และ isSameTree(left of p, left of q) เป็นจริง andisSameTree(ขวาของ p, right of q) เป็นจริง

  • คืนความจริง

• คืนค่าเท็จ

ตัวอย่าง

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

#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 Solution {
public:
   bool isSameTree(TreeNode *p, TreeNode* q){
      if (p == NULL && q == NULL)
         return true;
      if (p == NULL || q == NULL)
         return false;
      if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
         return true;
      return false;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3}, v1 = {1,2,3};
   TreeNode *root1 = make_tree(v);
   TreeNode *root2 = make_tree(v1);
   cout << (ob.isSameTree(root1, root2));
}

อินพุต

{1,2,3}, {1,2,3}

ผลลัพธ์

1