Leetcode 1261. 從受污染的二元樹中找出元素

這是 Leetcode 2025 年 2 月 21 日的每日一題。

題目描述
#

給定一棵二元樹，其原始規則如下：

root.val == 0
對於任意 treeNode：
1. 若 treeNode.val 為 x 且 treeNode.left != null，則 treeNode.left.val == 2 * x + 1
2. 若 treeNode.val 為 x 且 treeNode.right != null，則 treeNode.right.val == 2 * x + 2

現在這棵樹已被污染，也就是所有節點的值都變成了 -1。

請實作 FindElements 類別：

FindElements(TreeNode* root)：使用一棵受污染的二元樹初始化物件並恢復原始數值。
bool find(int target)：若目標值存在於已恢復的樹中，則回傳 true。

解題直覺
#

我們遍歷整棵樹並依照題目描述的規則更新每個節點的值。
更新後，將所有出現過的值存進一個哈希表中，以便快速查詢目標是否存在。

Code
#

class FindElements {
    private:
        unordered_map<int, bool> exist;
        void dfs(TreeNode* root, int val){
            if(!root){
                return;
            }
            else{
                root->val = val;
                exist[val] = true;
            }
            dfs(root->left, 2 * val + 1);
            dfs(root->right, 2 * val + 2);
        }

    public:
        FindElements(TreeNode* root) {
            dfs(root, 0);
        }
        
        bool find(int target) {
            return exist[target];
        }
};