如何从 Leetcode 值列表构造二叉树？

Question

对于以下问题：

输出/正确结果指定为：

 Output: [3,9,20,null,null,15,7]

我不确定该输出实际上代表什么。我尝试按级别扫描它。例如 3 是根，那么它的子元素是 9 和 20（这是行不通的）。那么真正的树是什么？

Answer 1

这就是二叉树的表示方式。

输出是一个节点列表，其中对于节点

i

（从索引 0 开始），节点

2*i+1

是其左子节点，节点

2*i+2

是其右子节点。因此，如果这些节点不存在，则列表中对应的值表示为

NULL

。

在本例中，节点 0 的值为 3，其左子节点显示在节点 1 (

Output[1]

) 中，值为 9，而其右子节点显示在节点 2 (

Output[2]

) 中，值为 20。

但是，节点 2（值为 20 的

Output[2]

）没有任何子节点，因此与其子节点（

Output[3]

、

Output[4]

）对应的值显示为

Null

。

Answer 2

我认为我们需要一个队列来存储要写入的父节点，我们可以使用索引来确定是写入父节点的左（奇）子节点还是右（偶）子节点。这是用python3编写的解决方案，它返回树的根节点。我测试了问题 437' 输入并解决了问题，这也可以解决您发布的输入。如果代码有任何问题，请告诉我，我很乐意提供帮助。

def buildTree(nodes: list) -> TreeNode:
    n = len(nodes)

    if n == 0:
        return None
    
    parentStack = collections.deque()
    root = TreeNode(nodes[0])
    curParent = root

    for i in range(1, n):
        if i % 2 == 1:
            if nodes[i] is not None:
                curParent.left = TreeNode(nodes[i])
                parentStack.append(curParent.left)
        else:
            if nodes[i] is not None:
                curParent.right = TreeNode(nodes[i])
                parentStack.append(curParent.right)
            
            curParent = parentStack.popleft()

    return root