How do I reconstruct a contaminated binary tree for this problem?

Use DFS starting from the root set to 0, recursively assign left child as 2*v+1 and right child as 2*v+2, visiting all nodes.

Why is a hash set needed in FindElements?

A hash set stores all recovered node values, allowing O(1) lookups for the find(target) queries.

Can BFS be used instead of DFS?

Yes, BFS can reconstruct the tree level by level, but DFS is often simpler for recursive value assignment.

How to handle null children during reconstruction?

Check for null nodes before recursion to avoid runtime errors and ensure only existing children receive computed values.

Does this pattern apply to trees with arbitrary missing nodes?

Yes, the parent-child value formula still works, but only assign values to existing nodes and skip null children.

#1261

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

在受污染的二叉树中查找元素

给出一个满足下述规则的二叉树： root.val == 0 对于任意 treeNode ：如果 treeNode.val 为 x 且 treeNode.left != null ，那么 treeNode.left.val == 2 * x + 1 如果 treeNode.val 为 x 且 tre…

哈希表树深度优先搜索广度优先搜索设计

题目描述

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

root.val == 0
对于任意 treeNode：
1. 如果 treeNode.val 为 x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
2. 如果 treeNode.val 为 x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

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

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

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

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["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

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
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

提示：

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

lightbulb

解题思路

方法一：DFS + 哈希表

我们先通过 DFS 遍历二叉树，将节点值恢复为原来的值，并将所有节点值存入哈希表中。然后在查找时，只需要判断哈希表中是否存在目标值即可。

时间复杂度方面，初始化时需要遍历二叉树，时间复杂度为 $O(n)$ ，查找时只需要判断哈希表中是否存在目标值，时间复杂度为 $O(1)$ 。空间复杂度 $O(n)$ 。其中 $n$ 为二叉树节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        def dfs(root: Optional[TreeNode]):
            self.s.add(root.val)
            if root.left:
                root.left.val = root.val * 2 + 1
                dfs(root.left)
            if root.right:
                root.right.val = root.val * 2 + 2
                dfs(root.right)

        root.val = 0
        self.s = set()
        dfs(root)

    def find(self, target: int) -> bool:
        return target in self.s


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Ask for reconstruction method and whether DFS or BFS is preferred.
question_mark
Check if candidate uses a hash set for fast find queries.
question_mark
Probe edge cases like missing left or right children and tree depth limits.

warning

常见陷阱

外企场景

error
Failing to correctly compute child values from parent nodes, leading to incorrect tree reconstruction.
error
Not handling null children and attempting to assign values, causing runtime errors.
error
Using traversal without a hash set, resulting in O(N) find queries instead of O(1).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Recovering a contaminated N-ary tree instead of a binary tree using similar value reconstruction rules.
arrow_right_alt
Supporting updates where new nodes are added to the recovered tree and find must reflect additions.
arrow_right_alt
Implementing the recovery with BFS instead of DFS to handle extremely wide trees more efficiently.

help

常见问题

外企场景

继续练习

#1123 最深叶节点的最近公共祖先 #987 二叉树的垂序遍历 #865 具有所有最深节点的最小子树