1261. Find Elements in a Contaminated Binary Tree

1261. Find Elements in a Contaminated Binary Tree #

Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

The binary tree is contaminated, and all treeNode.val have been changed to -1.

You need to restore the binary tree and implement the FindElements class:

FindElements(TreeNode* root) initializes the object with a contaminated binary tree, you need to restore it first.
bool find(int target) checks whether the target value target exists in the restored binary tree and returns the result.

Example 1:

Input:
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output:
[null,false,true]
Explanation:
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

Example 2:

Input:
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output:
[null,true,true,false]
Explanation:
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

Example 3:

Input:
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output:
[null,true,false,false,true]
Explanation:
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

Note:

TreeNode.val == -1
The height of the binary tree is not more than 20
The total number of nodes is in the range [1, 10^4]
The total number of calls to find() is in the range [1, 10^4]
$0 <= target <= 10^6$

Depth-First Search#

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
public:
    FindElements(TreeNode* root) {
        function<void(TreeNode *, int)> dfs = [&](TreeNode *node, int n) ->void {
            if (!node) {
                return;
            }
            node->val = n;
            mp[n] = 1;
            dfs(node->left, n * 2 + 1);
            dfs(node->right, n * 2 + 2);
        };
        dfs(root, 0);
    }
    
    bool find(int target) {
        return mp[target];
    }

    unordered_map<int, int> mp;
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

1261. Find Elements in a Contaminated Binary Tree

1261. Find Elements in a Contaminated Binary Tree#

Depth-First Search#

1261. Find Elements in a Contaminated Binary Tree #