为什么这个二叉树前序遍历返回 none

Question

您好，我正在尝试解决 leetcode 问题 1379。

这里是问题的陈述 + link:

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

这是我失败的解决方案尝试：

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

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if cloned:
            if cloned.val == target.val:
                return cloned
            self.getTargetCopy(original, cloned.left, target)
            self.getTargetCopy(original, cloned.right, target)

我不明白为什么这不起作用。

我认为我的解决方案是对树进行预序遍历，并在每个阶段询问克隆树中的节点是否存在，如果存在，它的值是否等于我们正在寻找的值？如果是，那么 return 那个节点，我们已经找到了我们正在寻找的节点。

如果没有则检查简单地继续检查树。由于树中的值保证是唯一的并且目标值保证在树中然后我正在访问每个节点那么这肯定可以找到答案。

然而它没有通过自动化测试，它甚至没有通过示例 1（如上图所示）并且说它正在 returning null.

我错过了什么？

编辑：

我尝试在每次函数调用时打印我的原始解决方案和参数：

__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 7, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 4, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 3, target = 3 )
None

因此也可以看到克隆树从 7 向下遍历到 4 然后检查 4 的左和右 child 都是 none，然后它检查 7 的右 child 3并确认它与目标相同，此时在调用 cloned.val=3 中，因此 return 语句应该 return 值为 3 的节点应该是正确的答案似乎 returning none 这甚至不是当时 cloned 的值（正如显示参数的打印语句所证明的那样）发生了什么事？

Answer 1

当 if 条件不成立时，您什么都不 return。

所以改变这两行：

self.getTargetCopy(original, cloned.left, target)
self.getTargetCopy(original, cloned.right, target)

收件人：

res = self.getTargetCopy(original, cloned.left, target)
if res:
    return res
return self.getTargetCopy(original, cloned.right, target)

甚至（使用短路）：

return (self.getTargetCopy(original, cloned.left, target)
     or self.getTargetCopy(original, cloned.right, target))

为什么这个二叉树前序遍历返回 none

Why is this binary tree preorder traversal returning none

algorithm

tree

binary-tree

traversal

python-3.x