1261. Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

1. root.val == 0
2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
3. If treeNode.val == 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.

• Time : O(1)
• Space : O(N)

/**
 * 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 {
    unordered_set<int> vals;
    void push(TreeNode* node, int val) {
        if(!node) return;
        vals.insert(val);
        push(node->left, (val<<1) + 1);
        push(node->right, (val<<1) + 2);
    }
public:
    FindElements(TreeNode* root) {
        push(root, 0);
    }

    bool find(int target) {
        return vals.count(target);
    }
};

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

• Time : O(logN)
• Space : O(1)

/**
 * 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 {
    TreeNode* root;
public:
    FindElements(TreeNode* root): root(root) {}
    vector<int> getBit(int n) {
        vector<int> res;
        while(n) {
            res.push_back(n & 1);
            n>>=1;
        }
        reverse(begin(res), end(res));
        return res;
    }
    bool find(int target) {
        if(target == 0) return root;
        TreeNode* node = root;
        vector<int> bit = getBit(target + 1);
        for(int i = 1; i < bit.size(); i++) {
            if(bit[i]) {
                if(!node->right) return false;
                node = node->right;
            } else {
                if(!node->left) return false;
                node = node->left;
            }
        }

        return node;
    }
};

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