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

Question

这是我画的

我显然遗漏了一些东西。如何包含数组索引 10 处的值？ 我将感谢您的帮助。

Answer 1

数组编码不能让您假设节点的子节点位于索引 i*2+1 和 i*2+2 处。如果编码树是完整二叉树，则情况如此，但如果不是，则不能使用此公式。

相反，您应该在构建树时跟踪树的底层，仅注册真实节点（而不是null）。然后将下一个子节点分布在（当时）底层的节点中，等等。这实际上是一种广度优先的遍历方法。

过程如下：

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

然后，只要有更多输入需要处理，就重复此操作：

• 将节点从队列中出列，
• 从输入中读取接下来的两个值，并为它们创建节点。如果输入中没有足够的剩余值，请改用 null。
• 将这两个节点作为子节点附加到您从队列中获取的节点
• 。那些不为 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，为它们创建节点，将它们附加到出队节点，并将这些子节点入队，我们得到：

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

在迭代 #2 之后（请注意，没有 null 入队） )：

        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

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