Return 二叉树的根到叶路径作为 Python 列表

Question

如果我使用字符串，我可以得到二叉树中的所有root-to-leaf路径。但是，如果我将我的数据结构更改为列表，我将无法这样做。任何建议都会有所帮助。

class Node:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    
def all_tree_paths_str(root, paths=[], path = ''):
    if root:
      path += str(root.val)
      
      if not root.left and not root.right:  # if reach a leaf
        paths.append(path)  # update paths  
      else:
        all_tree_paths_str(root.left, paths, path)
        all_tree_paths_str(root.right, paths, path)
    return paths

def all_tree_paths_list(root, paths=[], path = []):
    if root:
      path.append(root.val)
      
      if not root.left and not root.right:  # if reach a leaf
        paths.append(path)  # update paths  
        path = []
      else:
        all_tree_paths_list(root.left, paths, path)
        all_tree_paths_list(root.right, paths, path)
    return paths  

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f
 
print(all_tree_paths_str(a))
print(all_tree_paths_list(a))

对于上面的测试用例：

     a
   /   \
  b     c
 / \     \
d   e     f

我实际上是一个嵌套列表：

[['a', 'b', 'd'], ['a', 'b', 'e'], ['a', 'c', 'f']]

但是我的代码 (all_tree_paths_list) returns 输出如下：

[['a', 'b', 'd', 'e', 'c', 'f'], ['a', 'b', 'd', 'e', 'c', 'f'], ['a', 'b', 'd', 'e', 'c', 'f']]

我能得到的最接近的是使用字符串而不是列表 (all_tree_paths_str):

['abd', 'abe', 'acf']

我不明白为什么我的递归 returns 列表中的所有节点。正如@Leif 所建议的那样，它不应该那样做......但它确实如此。

Answer 1

您将 path 定义为一个字符串，因此您将返回一个字符串。

相反，将其定义为列表。

path = '' -> path=[]

path += str(root.val) -> path.append(str(root.val))

def all_tree_paths(root, paths=[], path = []):
    if root:
      path.append(str(root.val))
      
      if not root.left and not root.right:  # if reach a leaf
        paths.append(path)  # update paths  
        path = ''
      else:
        all_tree_paths(root.left, paths, path)
        all_tree_paths(root.right, paths, path)

    return paths

Answer 2

Whelp，以典型的 rubber duck 方式，在用头撞墙并失败地发布这个问题几个小时后，我设法编造了一个像样的答案。

问题是按照@Laif 的建议将路径转换为列表，但还在递归左右节点之前添加 root.val。

如果有人有更有效的方法，我很乐意看到它。

def all_tree_paths(root, paths = [], treepath = []):
  if not root:
      return

  if not root.left and not root.right:
      treepath.append(root.val)
      paths.append(treepath)
        
  if root.left:
    treepath_left = list(treepath)
    treepath_left.append(root.val)
    all_tree_paths(root.left, paths, treepath_left)

  if root.right:
    treepath_right = [*treepath]
    treepath_right.append(root.val)
    all_tree_paths(root.right, paths, treepath_right)
    
  return paths

我还没有完全理解，但这里的关键是展开 treepath_* = ... 的列表值。这可以通过将其类型转换为列表 (list) 或在其上使用 * 运算符来完成。

Answer 3

你的代码的问题是使用了可变的默认参数。这是一个演示：

def hello(name, d=[]):
    d.append(name)
    print(f"Hello {d}")

hello("Peter")
hello("Paul")
hello("Mary")

输出：

Hello ['Peter']
Hello ['Peter', 'Paul']
Hello ['Peter', 'Paul', 'Mary']

另外，这种问题如果用generator就更容易解决了。这就是我想出的：

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

    def is_leaf(self):
        return self.left is None and self.right is None

def traverse(root, path=None):
    if root is None:
        return

    path = path or tuple()
    path += (root.val,)
    if root.is_leaf():
        yield path
    yield from traverse(root.left, path)
    yield from traverse(root.right, path)

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

print(list(traverse(a)))

输出：

[('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'c', 'f')]

几点注意事项

我避免使用列表作为参数，而是使用 None。 None 不是可变的（可修改的）所以它是安全的。
yield from x() 是 shorthand for y in x(): yield y
我添加了 is_leaf 以使代码更清晰

Return 二叉树的根到叶路径作为 Python 列表

Return root-to-leaf paths of a binary tree as a Python list

python

algorithm

data-structures