ค้นหาองค์ประกอบใน Binary Tree ที่ปนเปื้อน (Find Elements in a Contaminated Binary Tree) ใน C++

สมมติเรามี binary tree ที่มีกฎดังนี้:

• root.val == 0
• ถ้า treeNode.val == x และมี left child: treeNode.left.val = 2 * x + 1
• ถ้า treeNode.val == x และมี right child: treeNode.right.val = 2 * x + 2

แต่ tree ถูกปนเปื้อน (contaminated) ทำให้ค่า val ของทุกโหนดกลายเป็น -1 เราต้อง กู้คืน (recover) binary tree ก่อน แล้วจึง implement class FindElements ดังนี้:

• FindElements(TreeNode* root) 初始化物件 ใช้ contaminated binary tree ต้องกู้คืนก่อน
• bool find(int target) คืนค่า true หาก target มีอยู่ใน tree ที่กู้คืนแล้ว

แนวทางแก้ปัญหา

1. สร้าง set<int> a เก็บค่าที่กู้คืนได้
2. สร้างฟังก์ชัน dfs() รับ root และ rootVal (เริ่มต้น -1)
3. ถ้า root เป็น null: return
4. ถ้า rootVal == -1: ตั้งค่า root->val = 0, มิฉะนั้น root->val = rootVal
5. ใส่ root->val ลงใน set a
6. เรียก dfs ซ้ำ: left ด้วย 2*val+1, right ด้วย 2*val+2
7. ตอน initialize เรียก dfs(root, -1)
8. ตอน find: ตรวจสอบว่ามี target ใน set a หรือไม่

ตัวอย่างโค้ดเต็ม

#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 tree with [-1,-1,-1,-1,-1], then call find(1), find(3), find(5)

Output

1
1
0

(true, true, false)