如何从级别顺序遍历创建二叉树？

Question

给定一个 level_order 列表，其中可以包含 None 个值，如何构造二叉树以遵循列表中的 None 个值，即 None 个节点可以没有任何 children（left 或 right 值）。

from typing import List, Optional

class Node():
    def __init__(val: int=None, left: Optional[Node]=None, right: Optional[Node]=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree(level_order: List, root=None): -> Node:
    pass

例如，当level_order是[4, -7, -3, None, None, -9, -3, 9, -7, -4, None, 6, None, -6, -6, None, None, 0, 6, 5, None, 9, None, None, -1, -4, None, None, None, -2]时，树应该是这样的

当 level_order 为 [1, 2, 3, 4, 5] 时，树应该看起来像

以下代码生成二叉树，但不考虑列表中的 None 值

def binary_tree(level_order, root=None):
    ls = []

    def insert_value(data, root):
        newnode = Node(data)
        if len(ls) != 0:
            temp = ls[0]

        if root is None:
            root = newnode

        elif temp.left is None:
            temp.left = newnode

        elif temp.right is None:
            temp.right = newnode
            _ = ls.pop(0)

        ls.append(newnode)
        return root

    for i in range(len(level_order)):
        root = insert_value(level_order[i], root)

    return root

但是上面的代码导致下面的树不正确

Answer 1

首先如何从树中获取节点的级别顺序列表？好吧，你 return 来自树的广度优先遍历的每个元素。要从层序列表重建树，那么，我们可以以广度优先的方式遍历树。

当我们插入每个元素时，从根开始，将其添加到队列中。然后，一旦我们完成添加节点的左右子节点，就从队列中拉出下一个节点。一旦我们运行没有要添加的元素，只需 return 根。

from typing import List, Optional

class Node():
    def __init__(self, val: int=None, left: Optional['Node']=None, right: Optional['Node']=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree(level_order: List) -> Node:
    values = iter(level_order)
    root = Node(next(values))
    nodes_to_fill = [root]
    try:
        while True:
            next_node = nodes_to_fill.pop(0)
            new_left = next(values)
            if new_left is not None:
                next_node.left = Node(new_left)
                nodes_to_fill.append(next_node.left)
            new_right = next(values)
            if new_right is not None:
                next_node.right = Node(new_right)
                nodes_to_fill.append(next_node.right)
    except StopIteration:
        return root

这与广度优先搜索使用的机制相同，除了在本例中我们使用它来构建树，而不是搜索吧。

为了稍微提高效率，如果您的树非常大，您可以使用 queue.Queue 而不是列表。

如何从级别顺序遍历创建二叉树？

How to create binary tree from level order traversal?

python

binary-tree