1261. Find Elements in a Contaminated Binary Tree

Problem

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
Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

Constraints:

• TreeNode.val == -1
• The height of the binary tree is less than or equal to 20
• The total number of nodes is between [1, 10^4]
• Total calls of find() is between [1, 10^4]
• 0 <= target <= 10^6

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

Example2

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

Solution

前序遍历，递归。但效率不高。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
public:
    FindElements(TreeNode* root) {
        inner_root = new TreeNode(0);
        
        recoverTree(root,inner_root);

    }

    void recoverTree(TreeNode* root,TreeNode* i_root)
    {
        if(root->left)
        {
            i_root->left = new TreeNode(2 * i_root->val + 1);
            recoverTree(root->left,i_root->left);
        }

        if(root->right)
        {
            i_root->right = new TreeNode(2 * i_root->val + 2);
            recoverTree(root->right,i_root->right);
        }
    }
    
    bool find(int target) {
        return find(inner_root,target);

    }

    bool find(TreeNode *root,int target)
    {
        if(!root)
            return false;
        if(root-> val == target)
            return true;
        return find(root->left,target) || find(root->right,target);
    }

    TreeNode* inner_root;

};

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