递归实现克隆二叉树对应节点查找时始终返回None的问题排查

问题描述 #

我在解决LeetCode题目1379.《找出克隆二叉树中的相同节点》时遇到了问题。题目要求：给定原始二叉树original、克隆二叉树cloned以及原始树中的目标节点target，返回克隆树中对应的节点。我有一份递归代码能通过所有测试用例，但另一种递归写法始终返回NULL，只通过了3/56个测试用例。我追踪到正确的if语句确实执行了，但就是得不到正确结果，想问问问题出在哪？

可正常运行的代码 #

if original is None and cloned is None:
    return None
if original.val == target.val and cloned.val == target.val:
    return cloned
return self.getTargetCopy(original.left, cloned.left, target) or self.getTargetCopy(original.right, cloned.right, target)

存在问题的代码 #

class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        """
        :type original: TreeNode
        :type cloned: TreeNode
        :type target: TreeNode
        :rtype: TreeNode
        """
        if original is None and cloned is None:
            return None
        if original.left and cloned.left:
            self.getTargetCopy(original.left, cloned.left, target)
        if original.val == cloned.val and original.val == target.val and cloned.val ==target.val:
            return cloned
        if original.right and cloned.right:
            self.getTargetCopy(original.right, cloned.right, target)

问题分析与解决 #

你的问题出在递归调用没有返回结果：

• 在有问题的代码里，当递归遍历左子树或右子树时，只是执行了self.getTargetCopy(...)，但没有把递归得到的结果返回给上层调用。比如目标节点在左子树时，递归函数确实找到了对应节点，但这个结果无法传递到上层，上层函数继续执行后续代码，最终默认返回None。
• 右子树的递归调用同样存在这个问题，即使找到目标节点，结果也无法向上传递。

而可正常运行的代码通过return ... or ...的逻辑，一旦左子树递归找到结果就直接返回，否则再遍历右子树，确保找到的结果能被正确传递回去。

修改后的正确代码示例：

class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        """
        :type original: TreeNode
        :type cloned: TreeNode
        :type target: TreeNode
        :rtype: TreeNode
        """
        if original is None and cloned is None:
            return None
        # 先检查当前节点是否为目标节点
        if original.val == target.val and cloned.val == target.val:
            return cloned
        # 遍历左子树，若找到结果直接返回
        left_res = self.getTargetCopy(original.left, cloned.left, target)
        if left_res:
            return left_res
        # 遍历右子树，返回结果（没找到则返回None）
        return self.getTargetCopy(original.right, cloned.right, target)

或者适配你原有结构的写法：

class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        """
        :type original: TreeNode
        :type cloned: TreeNode
        :type target: TreeNode
        :rtype: TreeNode
        """
        if original is None and cloned is None:
            return None
        if original.left and cloned.left:
            res = self.getTargetCopy(original.left, cloned.left, target)
            if res:
                return res
        if original.val == cloned.val and original.val == target.val and cloned.val == target.val:
            return cloned
        if original.right and cloned.right:
            res = self.getTargetCopy(original.right, cloned.right, target)
            if res:
                return res
        return None

内容的提问来源于stack exchange，提问作者Gingerbread