Tìm phần tử trong cây nhị phân bị nhiễm (Find Elements in a Contaminated Binary Tree) trong C++

Giả sử có một cây nhị phân với quy tắc:

• root.val == 0

• Nếu treeNode.val = x và treeNode.left không null, thì treeNode.left.val = 2 * x + 1

• Nếu treeNode.val = x và treeNode.right không null, thì treeNode.right.val = 2 * x + 2

Cây bị nhiễm: tất cả giá trị node bị đổi thành -1. Cần khôi phục cây và triển khai class FindElements:

• FindElements(TreeNode* root) Khởi tạo với cây bị nhiễm, khôi phục trước.

• bool find(int target) Trả về true nếu target tồn tại trong cây đã khôi phục.

Ví dụ: sau khi khôi phục, tìm 1, 3, 5 cho kết quả true, true, false.

Giải pháp:

• Định nghĩa set a lưu các giá trị đã khôi phục.

• Định nghĩa DFS(root, rootVal=-1).

• Nếu root null, return.

• Nếu rootVal == -1, gán root.val = 0, ngược lại gán rootVal.

• Thêm root.val vào set a.

• Gọi đệ quy cho left (2*val+1) và right (2*val+2).

• Khởi tạo: gọi dfs(root, -1).

• Tìm kiếm: kiểm tra target có trong set a.

Ví dụ hoàn chỉnh

#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 FindElements {
public:
    set<int> a;
    void dfs(TreeNode* root, int rootVal = -1) {
        if (!root) return;
        root->val = rootVal == -1 ? 0 : rootVal;
        a.insert(root->val);
        dfs(root->left, 2 * root->val + 1);
        dfs(root->right, 2 * root->val + 2);
    }
    FindElements(TreeNode* root) {
        dfs(root);
    }
    bool find(int t) {
        return a.find(t) != a.end();
    }
};
int main() {
    vector<int> v = {-1,-1,-1,-1,-1};
    TreeNode* root = make_tree(v);
    FindElements ob(root);
    cout << (ob.find(1)) << endl;
    cout << (ob.find(3)) << endl;
    cout << (ob.find(5)) << endl;
}

Input

Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)

Output

1 1 0