Tìm Nút Tương Ứng Của Cây Nhị Phân Trong Bản Sao Của Cây Đó Trong C++

Giả sử chúng ta có hai cây nhị phân original và cloned và một tham chiếu đến nút target trong cây gốc. Cây cloned là bản sao của cây gốc. Chúng ta phải tìm tham chiếu đến cùng nút đó trong cây cloned.

Ví dụ cây như hình, target = 3 → đầu ra 3.

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

• Định nghĩa phương thức solve(node1, node2, target).

• Nếu node1 null, trả về null.

• Nếu node1 == target và node1->val == node2->val, trả về node2.

• leftPart = solve(node1->left, node2->left, target).

• rightPart = solve(node1->right, node2->right, target).

• Trả về leftPart nếu không null, ngược lại rightPart.

• Từ phương thức chính: trả về solve(original, cloned, target).

Ví dụ (C++)

Hãy 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){
            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:
    TreeNode* solve(TreeNode* node1, TreeNode* node2, TreeNode* target){
        if(!node1) return NULL;
        if(node1 == target && node1->val == node2->val) return node2;
        TreeNode* leftPart = solve(node1->left, node2->left, target);
        TreeNode* rightPart = solve(node1->right, node2->right, target);
        return leftPart? leftPart : rightPart;
    }
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return solve(original, cloned, target);
    }
};

int main(){
    vector<int> v = {7,4,3,NULL,NULL,6,19};
    TreeNode *root = make_tree(v);
    TreeNode *cloned = make_tree(v);
    TreeNode *target = root->right; // Nút giá trị 3
    Solution ob;
    cout << (ob.getTargetCopy(root, cloned, target))->val;
}

Đầu vào

[7,4,3,null,null,6,19] 3

Đầu ra

3