二叉树递归操作中代码行为与变量命名问题咨询
关于LeetCode 1325题「Delete Leaves With a Given Value」递归实现的两个问题解答
问题1:主函数返回root与返回dfs结果的行为差异原因
以测试用例[1,1]为例,先梳理两种实现的执行逻辑:
直接返回root的问题(代码片段1)
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]: def dfs(root, target): if root is None: return None root.left = dfs(root.left, target) root.right = dfs(root.right, target) if not root.left and not root.right and root.val == target: root = None return return root dfs(root, target) return root
递归执行流程:
- 处理根节点的左子节点:左子节点是叶子且值等于target,
dfs返回None,根节点的left被设为None。 - 此时根节点左右子节点都为空,且值等于target,进入判断分支:把局部变量root设为
None并返回。 - 主函数仅调用
dfs(root, target)但未接收返回值,主函数中的root变量仍指向原根节点对象,最终返回未被修改引用的原节点,导致输出[1]而非预期空树。
返回dfs结果的正确性(代码片段2)
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]: def dfs(root, target): if root is None: return None root.left = dfs(root.left, target) root.right = dfs(root.right, target) if not root.left and not root.right and root.val == target: root = None return return root return dfs(root, target)
主函数直接返回dfs(root, target)的结果,当根节点需要被删除时,递归会返回None,从而正确更新根节点的引用,得到预期的空树。核心原因是Python中局部变量的赋值不会改变外部变量的引用,必须通过返回值传递更新后的节点引用。
问题2:用变量存储dfs结果而非直接赋值给root.left/root.right导致失效的原因
修改后的代码片段:
root_left = dfs(root.left, target) root_right = dfs(root.right, target)
原正确逻辑root.left = dfs(root.left, target)的作用是:将左子树递归处理后的结果(可能是None,代表左子节点被删除)赋值给当前节点的left属性,从而更新原树的结构。
如果只把结果存在变量里却不赋值回root.left和root.right,当前节点的左右子节点仍指向未处理的原树分支,递归处理的结果完全没有作用到原树上,所有该删除的叶子节点都不会被移除,自然所有测试用例失效。
内容的提问来源于stack exchange,提问作者user22222314
相关产品推荐
相关产品推荐

