LeetCode 1261 在受污染的二叉树中查找元素：还原树与「target + 1」二进制寻路
【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode
导读
本题（LeetCode 1261，Find Elements in a Contaminated Binary Tree）要求在一棵节点值全部被污染为-1的二叉树上先按给定递推规则还原节点值，再设计一个支持快速判断目标值是否存在的FindElements类。本文以 problems/1261.find-elements-in-a-contaminated-binary-tree.md 为主体，完整覆盖暴力递归、空间换时间（HashSet）与二进制寻路三种解法，并结合二叉树与二进制数位的关系推导出 O(1) 额外空间的查找方案。读完本文，你将掌握「用值加 1 后的二进制位在树上寻路」这一技巧，并能直接应用到 1104 二叉树寻路 等同类题型。
题目描述与规则
给出一个满足下述规则的二叉树：
root.val == 0- 如果
treeNode.val == x且treeNode.left != null，那么treeNode.left.val == 2 * x + 1 - 如果
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^4]之间 - 调用
find()的总次数在[1, 10^4]之间 0 <= target <= 10^6
前置知识
- 二进制：理解
target + 1的二进制表示如何编码了从根节点到目标节点的一条路径，是二进制寻路法的核心前提。 - 满二叉树/堆式索引的性质：若父节点值为
x，左子节点为2x + 1、右子节点为2x + 2，这本质上是堆（Heap）的 0-based 索引规律，与 1104 二叉树寻路 中利用的满二叉树性质同源。
解法一：暴力法（递归还原 + 递归查找）
思路
最直接的想法是：递归还原整棵树，把所有-1按规则改写为正确值；find时再递归遍历整棵树查找目标值。代码非常简单，但会超时（详见下文复杂度分析）。
代码
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class FindElements: node = None def __init__(self, root: TreeNode): def recover(node): if not node: return node; if node.left: node.left.val = 2 * node.val + 1 if node.right: node.right.val = 2 * node.val + 2 recover(node.left) recover(node.right) return node root.val = 0 self.node = recover(root) def find(self, target: int) -> bool: def findInTree(node, target): if not node: return False if node.val == target: return True return findInTree(node.left, target) or findInTree(node.right, target) return findInTree(self.node, target) # Your FindElements object will be instantiated and called as such: # obj = FindElements(root) # param_1 = obj.find(target)（对应原文档 problems/1261.find-elements-in-a-contaminated-binary-tree.md）
复杂度与超时原因
- 还原：每个节点访问一次，时间复杂度 O(N)，其中 N 为节点数（最多 10^4）。
- 单次
find：最坏情况要遍历整棵树，时间复杂度 O(N)。 - 总复杂度：
find总调用次数最多也是 10^4，最坏总代价 O(N × M) ≈ 10^4 × 10^4 = 10^8，在时间限制下很可能超时。
因此需要优化。原文档明确指出："上述代码会超时，我们来考虑优化"。
解法二：空间换时间（HashSet）
思路
既然瓶颈在find的线性遍历，就用空间换时间：还原树的同时，把所有节点值存入一个集合（set）。此后find只需一次哈希查找，时间复杂度 O(1)。
需要注意一个实现细节（原文档特别强调）：self.seen = set()不能放在__init__方法外侧定义为类属性。因为多个测试用例之间不会销毁FindElements的实例变量，若把集合定义为类级共享变量，会残留上一个用例的数据，导致错误结果。
代码
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class FindElements: def __init__(self, root: TreeNode): # set 不能放在init外侧。 因为测试用例之间不会销毁FindElements的变量 self.seen = set() def recover(node): if not node: return node; if node.left: node.left.val = 2 * node.val + 1 self.seen.add(node.left.val) if node.right: node.right.val = 2 * node.val + 2 self.seen.add(node.right.val) recover(node.left) recover(node.right) return node root.val = 0 self.seen.add(0) self.node = recover(root) def find(self, target: int) -> bool: return target in self.seen # Your FindElements object will be instantiated and called as such: # obj = FindElements(root) # param_1 = obj.find(target)（对应原文档 problems/1261.find-elements-in-a-contaminated-binary-tree.md）
复杂度分析
- 还原：O(N)（遍历每个节点并写入
set）。 find：O(1)（哈希查找）。- 空间：O(N)，需要一个
set保存全部节点值。原文档指出：这种解法可以 AC，但在数据量非常大时，可能 MLE（内存超限），因此继续优化。
解法三：二进制法（target + 1 寻路，O(1) 空间）
思路：如果先把所有数加 1 会怎么样？
这是一条非常巧妙的思路。观察还原后的二叉树节点值，若把每个值都加 1，则：
- 根节点：
0 + 1 = 1 - 左子节点：
(2x + 1) + 1 = 2(x + 1)，即父节点加 1 后左移一位，末位补 0； - 右子节点：
(2x + 2) + 1 = 2(x + 1) + 1，即父节点加 1 后左移一位，末位补 1。
换句话说，加 1 之后，这棵树变成了标准的1-based 堆索引结构：子节点索引 = 父节点索引 × 2（左）或 × 2 + 1（右）。于是「值加 1」后的二进制表示恰好编码了从根到该节点的路径：
- 二进制最高位的
1对应根节点； - 其后的每一位：
0表示往左走，1表示往右走。
举例：target = 9
target + 1 = 10，二进制表示为1010。忽略最高位1，剩余路径位为010：
0向左（根 → 左子）1向右（左子 → 右子）0向左（右子 → 左子）
按这条路径走，即可到达值9的节点。同理可验证：target = 2时2 + 1 = 3（二进制11），路径位为1，即从根向右一步到达值为2的节点，与题目示例 1 中find(2) == True一致。
代码
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class FindElements: node = None def __init__(self, root: TreeNode): def recover(node): if not node: return node; if node.left: node.left.val = 2 * node.val + 1 if node.right: node.right.val = 2 * node.val + 2 recover(node.left) recover(node.right) return node root.val = 0 self.node = recover(root) def find(self, target: int) -> bool: node = self.node for bit in bin(target+1)[3:]: node = node and (node.left, node.right)[int(bit)] return bool(node) # Your FindElements object will be instantiated and called as such: # obj = FindElements(root) # param_1 = obj.find(target)（对应原文档 problems/1261.find-elements-in-a-contaminated-binary-tree.md）
代码逐行拆解
bin(target + 1)：得到类似0b1010的字符串。[3:]：跳过前三个字符0b1，即同时去掉二进制前缀0b与最高位的1（最高位对应根节点），剩余的每一位就是从根出发的寻路指令。(node.left, node.right)[int(bit)]：bit为'0'时取node.left，为'1'时取node.right，相当于用下标索引替代了if/else。node = node and ...：利用短路求值——一旦node为None（路径上某一步该方向不存在子节点），后续表达式不再计算并保持None，find返回False。- 最终
bool(node)：路径走完仍为非空节点，说明目标值存在，返回True。
复杂度分析
- 还原：O(N)（与暴力法相同的递归还原过程）。
find：O(log target)（树高不超过 20，target <= 10^6，二进制位数有限，即沿树深度方向行走），远快于暴力法的 O(N)。- 空间：O(1)，除了递归还原时隐式的调用栈外，
find不需要任何额外数据结构，彻底规避了 HashSet 方案的 MLE 风险。
三种解法对比与选型建议
| 解法 | 还原复杂度 | find 复杂度 | 额外空间 | 结论 |
|---|---|---|---|---|
| 暴力法（递归遍历查找） | O(N) | O(N) | O(树高) | 总代价可能达 10^8，会超时 |
| 空间换时间（HashSet） | O(N) | O(1) | O(N) | 可以 AC，但大数据量下有 MLE 风险 |
| 二进制法（target + 1 寻路） | O(N) | O(log target) | O(1) | 时间、空间均衡，最优雅 |
工程上推荐：
- 若追求
find极致速度且内存充裕，选 HashSet 方案； - 若追求空间极致（或数据规模极大），选二进制寻路方案，且它无需额外建集合，
find的 O(log target) 在树高 ≤ 20 的限制下几乎可视为常数。
关键点解析
- 空间换时间：以 O(N) 的集合存储换取
find的 O(1) 查询，是"还原 + 多次查询"类题目最常见的优化方向。 - 二进制思维：将节点值整体加 1 后，树退化为 1-based 堆索引结构，
target + 1的二进制位直接编码了根到目标节点的路径——0向左、1向右。 - 将 target + 1：这一步是整个二进制法的题眼，务必理解"加 1"如何把
2x+1 / 2x+2的递推关系对齐到"左移 + 0/1 补位"的二进制规律上。 - 实例变量与类变量的坑：
set必须放在__init__内，避免测试用例间数据残留（原文档明确强调）。
仓库内的学习路径与延伸
该题被收录于本仓库的多种索引中，便于按难度与专题检索：
- collections/medium.md：归入中等难度（Medium）题单；
- SUMMARY.md 与 introduction.md：分别位于目录与简介的题解索引中；
- README.md：主 README 的题解目录同样收录本题。
与本题二进制思想强相关的姊妹题是 1104 二叉树寻路（Path In Zigzag Labelled Binary Tree）：它同样利用「值加 1 / 索引」与满二叉树层级（第 k 层最小值2^(level-1)、最大值2^level - 1）的性质，逆向求出根到节点的路径。将两题对照学习，可以系统掌握"二叉树索引与二进制位"这一通用套路。此外，二进制与位运算的系统性专题可参考 thinkings/bit.md，二叉树的遍历与结构基础可参考 thinkings/binary-tree-traversal.md。
小结
本题的核心递推left = 2x + 1、right = 2x + 2与堆索引完全同构，因此"值 + 1 的二进制位 = 路径"这一性质是天然成立的。从暴力递归 → HashSet 空间换时间 → 二进制寻路，三种解法展示了同一道题在不同约束（时间、内存）下的渐进式优化思路。掌握bin(target + 1)[3:]的写法与node and (node.left, node.right)[int(bit)]的短路技巧，你就能在 O(1) 额外空间内完成 O(log target) 的快速查找。
【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
——手撕GPT（零基础保姆级教学）)
