二叉树上的级别搜索遍历，递归调用返回错误的节点顺序

Question

假设我有一个二叉树，我想使用递归算法进行基于级别的遍历：

  .
└── 1/
    ├── 2/
    │   ├── 3/
    │   │   ├── 4
    │   │   └── 9
    │   └── 30
    └── 71/
        ├── 72
        └── 99

我编写这个算法的灵感来自于树算法的级别优先遍历，该算法在特定的输入深度处停止：

def get_subtree_from_rt(subtree, root_start, max_depth):
    if max_depth == 0:
        return []
    nodes = [root_start]
    if root_start == -1:
        return []
    else:
        nodes.extend([subtree.children_left[root_start], subtree.children_right[root_start]])
        print(nodes)
    nodes.extend(child for child in get_subtree_from_rt(subtree, subtree.children_left[root_start], max_depth - 1) if
                     child not in list(filter(lambda a: a != -1, nodes)))
    
    nodes.extend(child for child in get_subtree_from_rt(subtree, subtree.children_right[root_start], max_depth - 1) if
                     child not in list(filter(lambda a: a != -1, nodes)))
    return nodes

该算法确实遍历了树，但以不需要的顺序，即上述树的返回结果是：

[1, 2, 71, 3, 30, 4, 9]

虽然正确的应该是：

[1, 2, 71, 3, 30, 72, 99]

事实上，两次递归调用的

root_start

并不相同，因为第一个递归调用改变了它的值。 我的问题是如何获得上述结果，但避免对不同的

root_start

值调用第二个递归调用？

Answer 1

你的代码不是可重现的，而是IIUC，这里有一个可能的选项，使用

bigtree

：

from itertools import chain
from bigtree import (
    str_to_tree,
    levelordergroup_iter
)

tree_str = """
1/
├── 2/
│   ├── 3/
│   │   ├── 4
│   │   └── 9
│   └── 30
└── 71/
    ├── 72
    └── 99
"""

levels = list(
    map(
        int,
        chain.from_iterable(
            [
                [n.name.strip("/") for n in ng]
                for ng in levelordergroup_iter(str_to_tree(tree_str))
            ][:-1]
        ),
    )
)

输出：

print(levels) # [1, 2, 71, 3, 30, 72, 99]