Gộp Hai Cây Nhị Phân Trong C++

Giả sử chúng ta có hai cây nhị phân và khi đặt một cái đè lên cái kia, một số nút của hai cây bị chồng chéo trong khi những nút khác không. Chúng ta cần gộp chúng thành một cây nhị phân mới. Quy tắc gộp như sau: nếu hai nút bị chồng chéo, thì cộng giá trị của hai nút làm giá trị mới của nút đã gộp. Ngược lại, nút không rỗng sẽ được dùng làm nút của cây mới.

Ví dụ, nếu hai cây là:

Kết quả đầu ra sẽ là:

Các Bước Giải Quyết

• Phương thức là mergeTrees(). Nó nhận hai nút cây n1 và n2.
• Nếu n1 rỗng và n2 không rỗng, trả về n2; ngược lại nếu n2 rỗng và n1 không rỗng, trả về n1; nếu cả hai đều null, trả về null.
• Giá trị của n1 := giá trị của n1 + giá trị của n2.
• Con trái của n1 := mergeTrrees(con trái của n1, con trái của n2).
• Con phải của n1 := mergeTrees(con phải của n1, con phải của n2).
• Trả về n1.

Ví Dụ (C++)

Xem 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;
    }
};

int 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);
    return 0;
}

Đầu Vào

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

Đầu Ra

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