查找二叉树中指定节点的路径 (Python)

我在计算二叉树中从根到指定节点的路径时遇到问题（这是专门针对此问题的 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]

你可以看到我没有达到预期。我确信这与我的遍历算法有关，但我不知道我哪里出了问题。任何帮助是极大的赞赏。

失踪者4是由于您从未附加它而引起的。在您的成功案例中：

if root.val == k:
    return l

...你需要这样做：

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

额外的3 and 5是因为你always附加中间情况下的值，即使对于要回溯的节点也是如此。

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

# 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=[]):

That []这是默认值l被创建一次，当def被执行，然后在每次调用时重用。这意味着path2(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，但它still值得学习如何以尾部调用的方式做事，只是为了您自己的理解（当然，如果您用另一种语言编写代码）。但首先要学习如何做更简单的版本，然后才尝试反转它。