arrays - 将二叉树展平为数组 : Is there a way to find a node's index in the array when traversing depth-first?

Question

我想把二叉树压平

  2
 / \
1   4
   / \
  3   7

像这样的数组

{2, 1, 4, null, null, 3, 7}

这在我的理解中很常见，甚至可能是规范的。

我知道，如果我以广度优先 (BFS) 遍历树，例如，使用队列在我遇到节点时附加要访问的节点，那么构建这样的数组是自动的——BFS 排序正是数组。

但我想知道是否有一种方法可以在遍历深度优先(DFS)的同时构建数组。

我想出了一个不太奏效的方案:

1. 在递归遍历时，跟踪您所在的级别 (L)，以及您正确的次数> (R).
2. 然后索引由公式(2^L)-1+R给出。

不幸的是，这失败了，因为左右“转弯”的顺序很重要。

是否可以跟踪不同的状态以有效地生成索引？

Answer 1

如果我们使用从零开始的索引，那么深度 d 的节点(0 代表根，1 代表根的直接子节点，等等)从索引 2 开始 ^em>d−1.

在给定深度的“行”节点中，我们可以将每个“下降到左子节点”和“下降到右子节点”步骤视为一个位:左 = 0(前半部分)，右 = 1(下半场)。例如，如果我们从根节点开始并从左-左-右移动，那么我们将在深度为 3 的行中的位置 001₂ 结束，而如果我们从根节点开始然后从右-右-左移动，然后我们将在该行的第 110₂ 位置结束。

然后我们可以将行的起始索引添加到行内的位置以获得整体索引。

这是一些伪代码:

get_index(path):
    row_start := 0
    position_in_row := 0
    for element in path:
        row_start := 2 * row_start + 1
        position_in_row := 2 * position_in_row
        if element is 'RIGHT':
            position_in_row := position_in_row + 1
    return row_start + position_in_row

如果我们使用基于一个的索引，则将 row_start := 0 更改为 row_start := 1 和 row_start := 2 * row_start + 1 到 row_start := 2 * row_start。