获取使用深度优先遍历二叉树的迭代器

Question

我想使用 for 循环对二叉树进行深度优先遍历，并在每一步执行计算。

假设你有一个 4 层的树：

       root
       /  \
      /    \
     /      \
    xx       xx
   /  \     /  \
  /    \   /    \
xx    xx   xx    xx
/ \   / \  / \   / \
x  x x   x x  x  x  x

如果你把“深度优先探索树的步骤”放在一个列表中，它看起来像这样：

[
[1],
[1,1], 
[1,1,1],
[1,1,0],
[1,0],
[1,0,1],
[1,0,0],
[0], 
[0,1],
[0,1,0], 
[0,1,1],
[0,0],
[0,0,1]
[0,0,0] 
]

是否有一个函数，给定二叉树的层返回“步骤”列表中的“树探索”？

我的第一个想法是使用 itertools.permutation 库，但它没有给你正确的顺序。

我还尝试使用：

l = [False, True]
list(itertools.product(l, repeat=3))

Close 但它没有考虑到我在树的级别上上下下。

Answer 1

假设您的二叉树是一个完美二叉树，您可以使用此函数：

def traverse(height, left=1, right=0):
    path = []
    while True:
        if len(path) < height:
            path.append(left)
        else:
            while path[-1] == right:
                path.pop()
                if not path:
                    return
            path[-1] = right
        yield path

然后对高度为 3 的树按如下方式调用它：

for path in traverse(3):
    print(path)