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

Question

给定一个可以包含None值的level_order列表，如何根据列表中的None值构造二叉树，即None节点不能有任何子节点（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

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

当我们插入每个元素时，从根开始，将其添加到队列中。然后，在完成添加节点的左、右子节点后，从队列中拖出下一个节点。一旦要添加的元素用完，只需返回根

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而不是列表