这棵（不完整）树的数组表示是什么？

Question

根据LC，这棵树（我们称之为

a

）的数组表示是

a = [1, NULL, 2, 3]

但是，这违反了以下算法：位于

i

的位置

a

的根的左子节点位于位置

2*i

，而位于

i

的位置

a

的根的右子节点位于位置

2*i+1 

（来源）

我的问题是：

1. 在像上面这样的不完整树的情况下，您是否将所有缺失的节点写为 NA（除了二叉树的最末端）？在给出的解决方案中，并未写出所有丢失的节点。特别是

   1

   的左子节点缺失并表示为

   NULL

   ，但其子节点甚至不包含在数组表示中。因此，即使

   3

   是

   2

   的左孩子，它的位置 (

   4

   ) 并不遵循

   2*i

   的公式，其中 i 是

   2

   的位置。
2. 如果上面给出的解决方案（

   [1, NULL, 2, 3]

   ）是给定二叉树的正确数组表示，那么当所讨论的节点位于位置

   i

   时，识别节点子节点位置的公式是什么？缺失节点何时应该或不应该包含在不完全二叉树的数组表示中的规则是什么？

上下文：我正在尝试编写一种算法，该算法将树的数组表示形式作为输入并输出该树的有序遍历。

Answer 1

在像上面这样的不完整树的情况下，你是否将所有缺失的节点写为 NA（除了二叉树的最末端）？

我们在这里讨论序列化（LeetCode 内部使用的输入格式是text，而不是数组），序列化树的方法有很多种。

在 LeetCode 的格式中，序列化使用 JSON 格式，按照广度优先顺序，其中

null

（小写！）表示没有节点，而本来可以有节点。您想知道为什么节点 1 的左侧孙子在序列化格式中没有用

null

表示。 LeetCode 的格式不包含它们，因为它们不能是

null

以外的任何东西，因为它们的父级已经是

null

，因此它是冗余信息。确实，它违反了节点子节点位置位于

i*2

和

i*2+1

的公式，但该公式用于 不同 表示，通常用于二元堆。

如果上面给出的解 ([1, NULL, 2, 3]) 是给定二叉树的正确数组表示，那么当所讨论的节点位于位置 i 时，识别该节点的子节点位置的公式是什么？

没有直接的公式；当您拥有的唯一信息是父节点的索引时则不然。

缺失节点何时应该或不应该包含在不完全二叉树的数组表示中的规则是什么？

规则是：当它是（非空）父节点的直接子节点时，包含

null

。当父级不存在（空）时不要包含它。

我正在尝试编写一种算法，该算法将树的数组表示形式作为输入并输出该树的有序遍历。

解决此问题的最直接方法是首先使用典型的节点对象（具有左/右属性）构建树数据结构。然后在第二阶段产生您想要的遍历。

要创建基于节点的数据结构，您可以在数组表示上使用广度优先遍历，其中仅将非空节点推送到队列上。这是它的伪代码：

function makeTree(arr):
    if arr.length == 0:
        return null // empty tree
    nodes = [new TreeNode(arr[0])]
    for (j = 1, i = 0; j < arr.length; j++):
        node = arr[j] == null ? null : new TreeNode(arr[j])
        if j % 2 == 1:
            nodes[i].left = node
        else
            nodes[i].right = node
            i++
        if node != null:
            nodes.push(node)
    return nodes[0]

在回答其他问题时，我提供了该算法在 JavaScript 和 Python 中的实现。