给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

提示：

• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• 0 <= target <= 10^6

示例

输入： [“FindElements”,”find”,”find”,”find”]

[[[-1,-1,-1,-1,-1]],[1],[3],[5]]

输出：[null,true,true,false]

解释：

FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);

findElements.find(1); // return True

findElements.find(3); // return True

findElements.find(5); // return False

解法一（深度优先搜索 + 哈希表）

class FindElements:
    def __init__(self, root):
        self.valSet = set()
        self.dfs(root, 0)

    def find(self, target):
        return target in self.valSet

    def dfs(self, node, val):
        if node is None:
            return
        node.val = val
        self.valSet.add(val)
        self.dfs(node.left, val * 2 + 1)
        self.dfs(node.right, val * 2 + 2)

解法二：（深度优先搜索 + 位运算）

class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        self.dfs(root, 0)
        self.root = root

    def dfs(self, node: TreeNode, val: int):
        if node is None:
            return
        node.val = val
        self.dfs(node.left, val * 2 + 1)
        self.dfs(node.right, val * 2 + 2)

    def find(self, target: int) -> bool:
        target += 1
        k = target.bit_length() - 2
        node = self.root
        while k >= 0 and node is not None:
            if (target & (1 << k)) == 0:
                node = node.left
            else:
                node = node.right
            k -= 1
        return node is not None

解法三：（层序遍历 + 二分查找）

class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        self._nodes = []
        root.val = 0
        cur_level_nodes = [root]
        nxt_level_nodes = []
        while cur_level_nodes:
            nxt_level_nodes = []
            for node in cur_level_nodes:
                self._nodes.append(node.val)
                if node.left:
                    node.left.val = node.val * 2 + 1
                    nxt_level_nodes.append(node.left)
                if node.right:
                    node.right.val = node.val * 2 + 2
                    nxt_level_nodes.append(node.right)
                cur_level_nodes = nxt_level_nodes

    def find(self, target: int) -> bool:
        # Bi-search
        left, right, mid = 0, len(self._nodes) - 1, 0
        while left <= right:
            mid = (left + right) // 2
            if self._nodes[mid] == target:
                return True
            elif self._nodes[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return False