Chương trình gộp hai cây nhị phân trong C++

Giả sử có hai cây nhị phân và xét khi đặt cái này lên cái kia, một số nút của hai cây bị chồng lấn trong khi những nút khác không chồng lấn. Ta phải 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 chồng lấn, cộng giá trị 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ụ cây:

Kết quả gộp:

Để giải quyết, ta làm theo các bước sau:

• Phương pháp solve(). Nhận hai nút n1 và n2. Như sau:
• 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 null trả về null
• giá trị n1 := giá trị n1 + giá trị n2
• left của n1 := solve(left của n1, left của n2)
• right của n1 := solve(right của n1, right của n2)
• trả về n1

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include<bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v) {
        val = v;
        left = right = NULL;
    }
};

void inord(TreeNode *root) {
    if (root != NULL) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}

class Solution {
public:
    TreeNode* solve(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 = solve(n1->left, n2->left);
        n1->right = solve(n1->right, n2->right);
        return n1;
    }
};

int main() {
    TreeNode *root1 = new TreeNode(1);
    root1->left = new TreeNode(3);
    root1->right = new TreeNode(2);
    root1->left->left = new TreeNode(5);
    TreeNode *root2 = new TreeNode(2);
    root2->left = new TreeNode(1);
    root2->right = new TreeNode(3);
    root2->left->right = new TreeNode(4);
    root2->right->right = new TreeNode(7);
    Solution ob;
    TreeNode *root_res = ob.solve(root1, root2);
    inord(root_res);
    return 0;
}

Đầu vào

TreeNode *root1 = new TreeNode(1); root1->left = new TreeNode(3); root1->right = new TreeNode(2); root1->left->left = new TreeNode(5); TreeNode *root2 = new TreeNode(2); root2->left = new TreeNode(1); root2->right = new TreeNode(3); root2->left->right = new TreeNode(4); root2->right->right = new TreeNode(7);

Đầu ra

5 4 4 3 5 7