Hợp nhất hai cây nhị phân trong C ++

Giả sử chúng ta có hai cây nhị phân và xem xét rằng khi chúng ta đặt một trong số chúng để che đi cây kia, một số nút của hai cây bị chồng lên nhau trong khi các nút khác lại chồng lên nhau. Chúng ta phải hợp nhất chúng thành một cây nhị phân mới. Quy tắc hợp nhất là như vậy nếu hai nút chồng lên nhau, thì tính tổng các giá trị của nút thành giá trị mới của nút đã hợp nhất. Nếu không, nút không trống sẽ được sử dụng làm nút của cây mới.

Vì vậy, nếu cây cối -

Sau đó, đầu ra sẽ là -

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

• Phương thức là mergeTrees (). Điều này lấy hai nút cây n1 và n2. Điều này giống như

• nếu n1 trống và n2 khác rỗng thì trả về n2, ngược lại khi n2 trống và n1 là không trống thì trả về n1 và khi cả hai đều rỗng thì trả về null

• giá trị của n1:=giá trị của n1 + giá trị của n2

• left of n1:=mergeTrees (left of n1, left of n2)

• right of n1:=mergeTrees (right of n1, right of n2)

• trả về n1

Ví dụ (C ++)

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 = 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){
         temp->left = new TreeNode(val);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         temp->right = new TreeNode(val);
         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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr->val == 0){
            cout << "null" << ", ";
         }
         else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   TreeNode* mergeTrees(TreeNode* n1, TreeNode* n2) {
      if(!n1 && n2){
         return n2;
      }
      else if(!n2 && n1)return n1;
      else if(!n1 && !n2)return NULL;
      n1->val+=n2->val;
      n1->left = mergeTrees(n1->left,n2->left);
      n1->right = mergeTrees(n1->right,n2->right);
      return n1;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {1,3,2,5};
   vector<int> v2 = {2,1,3,NULL,4,NULL,7};
   TreeNode *root1 = make_tree(v1);
   TreeNode *root2 = make_tree(v2);
   root1 = ob.mergeTrees(root1, root2);
   tree_level_trav(root1);
}

Đầu vào

[1,3,2,5]
[2,1,3,null,4,null,7]

Đầu ra

[3, 4, 5, 5, 4, null, 7, ]