2026/9/18 13:49:38
FEATURED · 精选文章 
LeetCode 1261 在受污染的二叉树中查找元素还原树与「target 1」二进制寻路【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本题LeetCode 1261Find 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。findO(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 9target 1 10二进制表示为1010。忽略最高位1剩余路径位为0100向左根 → 左子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(target1)[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路径上某一步该方向不存在子节点后续表达式不再计算并保持Nonefind返回False。最终bool(node)路径走完仍为非空节点说明目标值存在返回True。复杂度分析还原O(N)与暴力法相同的递归还原过程。findO(log target)树高不超过 20target 10^6二进制位数有限即沿树深度方向行走远快于暴力法的 O(N)。空间O(1)除了递归还原时隐式的调用栈外find不需要任何额外数据结构彻底规避了 HashSet 方案的 MLE 风险。三种解法对比与选型建议解法还原复杂度find 复杂度额外空间结论暴力法递归遍历查找O(N)O(N)O(树高)总代价可能达 10^8会超时空间换时间HashSetO(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如何把2x1 / 2x2的递推关系对齐到左移 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），仅供参考
LeetCode 1261 在受污染的二叉树中查找元素：还原树与「target + 1」二进制寻路
LeetCode 1261 在受污染的二叉树中查找元素还原树与「target 1」二进制寻路【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本题LeetCode 1261Find 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。findO(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 9target 1 10二进制表示为1010。忽略最高位1剩余路径位为0100向左根 → 左子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(target1)[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路径上某一步该方向不存在子节点后续表达式不再计算并保持Nonefind返回False。最终bool(node)路径走完仍为非空节点说明目标值存在返回True。复杂度分析还原O(N)与暴力法相同的递归还原过程。findO(log target)树高不超过 20target 10^6二进制位数有限即沿树深度方向行走远快于暴力法的 O(N)。空间O(1)除了递归还原时隐式的调用栈外find不需要任何额外数据结构彻底规避了 HashSet 方案的 MLE 风险。三种解法对比与选型建议解法还原复杂度find 复杂度额外空间结论暴力法递归遍历查找O(N)O(N)O(树高)总代价可能达 10^8会超时空间换时间HashSetO(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如何把2x1 / 2x2的递推关系对齐到左移 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），仅供参考 
