Leetcode 1261. Find Elements in a Contaminated Binary Tree

This is the daily question of leetcode in 2025-02-21. {: .prompt-info }

Problem Description

#

Given a binary tree with the following rules:

1. root.val == 0
2. For any treeNode:
   1. If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
   2. If treeNode.val has a value x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

Implement the FindElements class:

• FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
• bool find(int target) Returns true if the target value exists in the recovered binary tree.

Intuition

#

1. We traverse all the nodes of the tree and update their values to satisfy the constraints given in the problem.
2. After modifying the values, we store them in a hash map to keep track of which values exist in the tree.

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];
        }
};

Thank you for reading! Let me know your thoughts and feedback! {: .prompt-tip }