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

Question

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

举个例子。给定下面的二叉树，如果我指定值为 4 的节点，我想 return [1, 2, 4]。如果我指定值为5的节点，我想return [1, 2, 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 是由于您总是在中间情况下追加值，即使对于您所在的节点也是如此要倒退了。

如果任一递归调用 return 是 non-empty 列表，您可以通过仅附加它来修复该问题，但是当然您会使节点乱序。最简单的解决方法是故意使节点乱序：

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

当 def 执行时，l 的默认值 [] 被创建一次，然后在每次调用时重复使用。这意味着 path2(a, 4) 第一次会 return 正确答案，[1, 2, 4]，但是当你第二次调用它时，它会继续附加到同一个列表并且 return [1, 2, 4, 1, 2, 4].

有几个惯用的方法解决这个问题，但在我们的例子中，因为我们已经在使用那个 path2 包装器函数，所以我们不妨就在那里修复它：

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

… 然后去掉 path.

上的默认值

但是，您可能需要考虑使用 easier-to-understand 版本重新开始：

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 []

（你可以把它写得更短一些；我特意把这里的一切都说清楚了。）

对于许多递归问题，将它们取反并传递一个累加器是一项重要的优化，因为 tail-call 消除可以从堆栈中删除一个分支。尽管 Python 不执行 TCE，但仍然值得学习如何以 tail-calling 方式做事，仅供您自己理解（以防万一当然，永远不要用另一种语言编写代码）。但是先学习如何做更简单的版本，然后再尝试反转它。

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

Find Path to Specified Node in Binary Tree (Python)

python

binary-tree

depth-first-search

tree-traversal