使用Python使用递归DFS打印路径

Question

我编写了这段代码，使用递归 DFS 打印二叉树中从

root

到

target

节点的路径：

    def dfs(self, current, target, path=[]):
        if current == None:
            path = []
            return False
        elif current.val == target.val:
            return True
        else:
            path.append(current.val)
            return self.dfs(current.left, target, path) or 
                   self.dfs(current.right, target, path)
 

当我运行此代码时，我注意到

path

变量有一个 所有节点 的列表，它遍历该列表以到达

target

节点，而不仅仅是从

root

到

target

的直接路径。我缺少什么？我知道我可能会错过在某个地方重置

path

变量，但我不确定..

Answer 1

存在以下问题：

• 语法问题（可能是因为您在帖子中更改了它）：最后一个语句分为两行，这是不允许的。如果您需要，请添加大括号，或在这两行的第一行后面附加

  \

  。

• path = []

  （在第一个

  if

  块内）是一个无用的语句：它只是为本地

  path

  名称分配一个新值，并且不再使用它。也许你认为它会改变

  caller

  的 path，但 assignment 在 Python 中永远不会这样做。另一方面，如果您 mutate

  path

  已引用的列表，那么这就是发生变化的调用者列表。例如，这就是发生的事情

  append

  。但即使在这种情况下您必须清空调用者的列表，这也不是正确的逻辑，因为目标节点可能仍然位于具有一些相同祖先的路径上。简而言之，这个

  path = []

  语句应该被删除。

• 路径将在访问时附加节点，即使两个递归调用返回

  False

  ，并且当前调用返回

  False

  ，该节点仍将保留在路径上。您应该将其从路径中删除——并且仅删除 that 节点。

• 为

  path

  参数指定默认值

  []

  是一个坏主意。这意味着，如果您不传递此参数，则将使用此默认列表，并且如果您在没有该参数的情况下进行 another 调用，它仍将是该列表。这将混合两个不同搜索的结果。相反，您可以使用

  None

  作为默认值，并让代码在发现它是

  None

  时将其设置为新的空列表。

• 不是问题，但将目标节点附加到路径中也是有意义的。

因此，通过这些修复，您的代码将如下所示：

    def dfs(self, current, target, path):
        if current is None:
            return False
        # Append the node's value, also when it is the target:
        path.append(current.val)
        if current.val == target.val:
            return True
        if (self.dfs(current.left, target, path) or 
                self.dfs(current.right, target, path)):
            return True 
        # If recursive calls were unsuccessful, remove current
        #    node from the path
        path.pop()
        return False

现在就可以了。尽管如此，我还是建议一些改变。

我根本不会使用

path

参数：原始调用者首先必须创建一个

path

（设置为空列表）然后将其提供给此函数，这是不直观的。该函数本身应该处理这个问题。

具有返回路径的功能。您现在返回的布尔值可以删除：如果未找到目标，则返回

None

，而当找到目标 was 时返回列表（路径）。

您只能在实际找到目标时开始构建路径，然后在从递归中展开时，将祖先节点添加到该路径，而不是追加然后再次弹出（因为尚未找到目标）。因此，不要以先序方式构建路径，而是以后序方式构建路径。

以下是如何实现这个想法：

    def dfs(self, current, target):
        def recur(current):
            if current is None:
                return
            if current.val == target.val:
                return [target]  # Start the path from the last node backwards
            reversed_path = recur(current.left) or recur(current.right)
            if reversed_path:
                # Append an ancestor once the target was found:
                reversed_path.append(current)
                return reversed_path
                
        reversed_path = recur(current)
        # Don't return a boolean, but the path or None 
        if reversed_path:
            return reversed_path[::-1]

使用此变体，调用者不得提供

path

参数，而是获取路径作为返回值。他们应该检查这个

path

是否是

None

，这表明没有找到目标节点。