在二叉树(Python)中查找指定节点的路径 [英] Find Path to Specified Node in Binary Tree (Python)

问题描述

我在计算从根到二叉树中指定节点的路径时遇到了麻烦(这是专门针对此问题的Python解决方案).

I'm having trouble computing the path from the root to a specified node in a binary tree (this is specifically about a Python solution to this problem).

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

Here's an example. Given the binary tree below, if I specify the node whose value is 4, I want to return [1, 2, 4]. If I specify the node whose value is 5, I want to return [1, 2, 5].

       1
     /  \
   2      3
 /  \
4    5

这是我尝试的解决方法.

Here's my attemped solution.

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]

您可以看到我没有达到预期.我敢肯定这与我的遍历算法有关，但我无法弄清楚哪里出了问题.任何帮助将不胜感激.

You can see that I don't get the expected. I'm sure it has to do with my traversal algorithm, but I can't figure out where I'm going wrong. Any help is greatly appreciated.

推荐答案

缺少4的原因是您从未添加它.在您的成功案例中:

The missing 4 is caused by the fact that you never append it. In your success case:

if root.val == k:
    return l

...您需要这样做:

… you need to d this:

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

---

额外的3和5是由于您总是在中间情况下附加值，甚至对于您要回溯的节点也是如此.

---

The extra 3 and 5 are caused by the fact that you always append the value in the intermediate case, even for the nodes where you're going to backtrack.

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

You can fix that by only appending it if either of the recursive calls returns a non-empty list, but then of course you'll have the nodes out of order. The easiest fix for that is to intentionally get the nodes out of order:

# 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)

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

… and then reverse the list at the end, e.g., in a wrapper function:

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

---

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

---

However, there's still one problem left in your code, right here:

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

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

That [] that's the default value for l gets created one time, when the def is executed, and then reused on every call. That means that path2(a, 4) will return the right answer the first time, [1, 2, 4], but when you call it a second time, it'll keep appending to that same list and return [1, 2, 4, 1, 2, 4].

有两种惯用的方法，但是在我们的情况下，由于我们已经在使用path2包装函数，因此我们不妨将其修复:

There are a couple idiomatic ways around this, but in our case, since we're already using that path2 wrapper function, we might as well just fix it there:

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

…，然后删除path上的默认值.

… and then get rid of the default value on path.

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

However, you might want to consider starting over with an easier-to-understand version:

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

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

(You can make this is a bit shorter; I went out of my way to make everything explicit here.)

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

For many recursive problems, inverting them and passing up an accumulator is an important optimization, because tail-call elimination can remove one of the branches from the stack. Even though Python doesn't do TCE, it's still worth learning how to do things the tail-calling way, just for your own understanding (and in case you ever write code in another language, of course). But learn how to do the simpler version first, and only then try to invert it.

这篇关于在二叉树(Python)中查找指定节点的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！