【LeetCode第 163 场周赛】5264. Find Elements in a Contaminated Binary Tree

版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/103117723

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.

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-elements-in-a-contaminated-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力生成树的数据，再用map去查，，，

/**
 * 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:
    map<int,bool> mp;
    FindElements(TreeNode* root) {
        root->val=0;
        mp[0]=1;
        init(root);
    }
    void init(TreeNode* root){
        if(root->left!=NULL){
            root->left->val=2*root->val+1;
            mp[2*root->val+1]=1;
            init(root->left);
        }
        if(root->right!=NULL){
            root->right->val=2*root->val+2;
            mp[2*root->val+2]=1;
            init(root->right);
        }
    }
    
    bool find(int target) {
        return mp[target];
    }
};

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