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

How to create binary tree from level order traversal?(如何从层次顺序遍历生成二叉树?)

本文介绍了如何从层次顺序遍历生成二叉树?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

给定一个level_order列表(可以包含None值),如何按照列表中的None值构建二叉树,即None节点不能有任何子节点(leftright值)。

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

这篇关于如何从层次顺序遍历生成二叉树?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:如何从层次顺序遍历生成二叉树?

基础教程推荐