Cùng một cây trong C ++

Giả sử chúng ta có hai cây nhị phân; chúng ta phải xác định một hàm để kiểm tra xem chúng có giống nhau hay không. Chúng ta biết rằng các cây nhị phân được coi là giống nhau khi chúng giống nhau về cấu trúc và các nút có cùng giá trị.

Vì vậy, nếu đầu vào giống như [1,2,3], [1,2,3], thì đầu ra sẽ là True

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm được gọi là isSameTree, hàm này sẽ sử dụng hai nút cây p và q

• nếu p giống NULL và q giống NULL thì -

  • trả về true

• nếu p giống NULL hoặc q giống NULL thì -

  • trả về false

• nếu val của p giống val của p và isSameTree (trái của p, trái của q) là đúng vàisSameTree (phải của p, phải của q) là đúng, thì

  • trả về true

• trả về false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

1