在二叉树（Python）中查找指定节点的路径

Question

我在计算从根到二叉树中指定节点的路径时遇到了麻烦（这特别是关于此问题的Python解决方案）。

这是一个例子。给定下面的二叉树，如果我指定值为4的节点，我想返回[1、2、4]。如果我指定值为5的节点，我想返回[1、2、5]。

       1
     /  \
   2      3
 /  \
4    5

这是我尝试的解决方案。

class TreeNode:
 def __init__(self, x):
     self.val = x
     self.left = None
     self.right = None

def path(root, k, l=[]):
    if not root:
        return []
    if root.val == k:
        return l

    # Pre-order traversal: Visit root, then left, then right.
    l.append(root.val)
    path(root.left, k, l)
    path(root.right, k, l)
    return l

现在如果我运行这个

>>> a = TreeNode(1)
>>> b = TreeNode(2)
>>> c = TreeNode(3)
>>> d = TreeNode(4)
>>> e = TreeNode(5)
>>> a.left = b
>>> a.right = c
>>> b.left = d
>>> b.right = e
>>> path(a, 4) # should be [1, 2, 4]
[1, 2, 5, 3]

您可以看到我没有达到预期。我确定这与我的遍历算法有关，但是我无法弄清楚哪里出了问题。任何帮助是极大的赞赏。

Answer 1

丢失4是由于您从未附加它而导致的。在您的成功案例中：

if root.val == k:
    return l

…您需要这样做：

if root.val == k:
    l.append(root.val)
    return l

多余的3和5是由于您总是在中间情况下附加值，即使对于要回溯的节点也是如此。

您可以通过仅在两个递归调用中的任何一个返回非空列表时附加它来解决此问题，但是当然，您将使节点混乱。最简单的解决方法是有意使节点混乱：

# Pre-order traversal: Visit root, then left, then right.
if path(root.left, k, l) or path(root.right, k, l):
    l.append(root.val)

…然后在末尾反转列表，例如在包装函数中：

def path2(root, k):
    return list(reversed(path(root, k)))

但是，您的代码中仍然存在一个问题，就在这里：

def path(root, k, l=[]):

那是执行时创建一次[]的默认值，然后在每次调用时重用。这意味着它将在第一次返回正确的答案，但是当您第二次调用它时，它将继续追加到相同的列表并返回。ldefpath2(a, 4)[1, 2, 4][1, 2, 4, 1, 2, 4]

有两种惯用的方法可以解决此问题，但是在我们的情况下，由于我们已经在使用该path2包装函数，因此不妨在此进行修复：

def path2(root, k):
    return list(reversed(path(root, k, [])))

…然后删除上的默认值path。

但是，您可能要考虑从一个易于理解的版本开始：

def path(root, k):
    if not root:
        return []
    if root.val == k:
        return [root.val]
    res = path(root.left, k)
    if res:
        return [root.val] + res
    res = path(root.right, k)
    if res:
        return [root.val] + res
    return []

（您可以将其缩短一些；我竭尽全力在此处将所有内容都明确了。）

对于许多递归问题，将它们求逆并经过一个累加器是一项重要的优化，因为消除尾部调用可以从堆栈中删除一个分支。即使Python不执行TCE，仍然值得学习如何以尾部调用的方式进行操作，只是为了您自己的理解（当然，如果您曾经用另一种语言编写代码）。但是，首先要学习如何制作更简单的版本，然后才尝试对其进行反转。