如何绘制此输入的二叉树：[1,2,2,3,null,null,3,4,null,null,4]？

Question

这是我画的

我显然遗漏了什么。如何包含数组索引 10 处的值？ 我会很感激你的帮助。

Answer 1

数组编码不是这样的，您可以假设节点的 children 位于索引 i*2+1 和 i*2+2 处。如果编码树是 complete 二叉树，那将是正确的，但如果不是，则不能使用此公式。

相反，您应该在构建树时跟踪树的底层，仅注册 真实 个节点（而不是 null）。然后把下一个children分布在（then）底层的节点之间等等，这真是一个breadth-first的遍历方式

这是程序：

创建一个队列，并为输入列表中的第一个值创建一个节点（如果列表不为空），并将其入队。

然后重复，只要有更多的输入要处理：

• 从队列中取出一个节点
• 从输入中读取接下来的两个值，并为它们创建节点。如果输入中没有足够的剩余值，请改用 null。
• 将这两个节点作为 children 附加到您从队列中取出的节点
• 那些 children 不是 null 的应该在队列中排队。

如果将此算法应用于示例输入 [1,2,2,3,null,null,3,4,null,null,4]，那么我们首先得到根，它放在队列。所以就在循环开始之前我们有：

        root: 1        queue = [1]
                       remaining input = [2,2,3,null,null,3,4,null,null,4]

我在这里用数字描述了队列内容，但它们确实是节点实例。

在循环的第一次迭代之后，我们从输入中读取 2 和 2，为它们创建节点，将它们附加到出队节点，并将这些 children 入队，我们得到：

        root: 1        queue = [2, 2]
             / \       remaining input = [3,null,null,3,4,null,null,4]
            2   2

迭代 #2 后（注意没有空值入队）：

        root: 1        queue = [2, 3]
             / \       remaining input = [null,3,4,null,null,4]
            2   2
           / *
          3    

第 3 次迭代后：

        root: 1        queue = [3, 3]
             / \       remaining input = [4,null,null,4]
            2   2
           / * * \
          3       3

第 5 次迭代后：

        root: 1        queue = [3, 4]
             / \       remaining input = [null,4]
            2   2
           / * * \
          3       3
         / *
        4

最终迭代后：

        root: 1        queue = [4, 4]
             / \       remaining input = []
            2   2
           / * * \
          3       3
         / *     * \
        4           4

队列不为空，但由于没有更多的输入，那些排队的节点代表不需要进一步处理的叶子。