如何从层次顺序遍历生成二叉树？

问题描述

给定一个level_order列表(可以包含None值)，如何按照列表中的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

但是上面的代码会产生以下错误的树

---

解决方案

首先如何从树中获取节点的级别排序列表？那么，您将返回广度优先遍历树中的每个元素。若要从级别排序列表重新生成树，则可以以广度优先的方式遍历树。

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

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