algorithm - 从列表重建一棵树，深度信息封装在列表的条目中

Question

我们通过深度优先遍历从一棵树(不一定一定是二叉搜索树)构建了一个列表。

里面的每个条目都是一对(k, d)，k是一个节点的键，d是那个节点的深度。

现在我们需要从列表中构造出原来的树。

我们该怎么做？

---

注意

1. 树不一定是二叉搜索树
2. 我们不知道深度优先遍历是前序、中序还是后序。

---

我的问题是

• 我们能否在条件下实现这种逆向工程？我知道对于二叉搜索树，我们至少需要两个遍历列表(例如，中序列表和后序列表)来重建原始树。
  • 怎么样？如果可能的话

Answer 1

注意事项:

• 中序遍历产生唯一的树

• 预购和后购不:

  你无法区分这两者:

    1    1
   /      \
  2        2
  

  我只生成左边的那个(这样做会容易很多)。

我们可以马上说的:

• 如果第一个节点是根节点(即深度不是 0):

  我们要么对空的左子树进行有序处理，要么进行预排序。

• 如果最后一个节点是根:

  我们要么对空的右子树进行中序处理，要么进行后序处理。

• 如果以上都不是:

  我们正在进行中序遍历。

对于上面我们不知道要进行哪种遍历的两种情况，最简单的方法是尝试为两种可能的遍历生成树，并丢弃不起作用的那个(基于以下限制)，如果有的话。

一些限制:

对于有序，如果当前节点为空，我们不能向右或向上。

对于预购，如果当前节点为空，则不能向左或向右移动。

对于后序，我们必须在设置当前节点后向上移动——我们不能在没有设置当前节点的情况下向左或向右移动。

在所有情况下，我们都尝试先向左走，然后再向右走。

“向左走”或“向右走”是指创建一个(空的)左或右子节点并遍历到该节点。
“向上”是指在已创建的树中简单地向上遍历。

基于以上限制，应该很容易写出生成树的算法。作为有序的例子:

1. 如果新节点的深度比当前节点的深度深:
   1. 如果当前节点为空且没有左 child ，我们可以创建一个左 child 并将其设置为当前节点
   2. 否则，如果当前节点不为空且没有右 child ，我们可以创建一个右 child 并将其设置为当前节点
2. 否则，如果深度与当前节点相同且当前节点为空，
   将该节点的值设置为新节点
3. 如果以上情况均未触发且当前节点为空，
   设置当前节点的父节点为当前节点
4. 如果以上情况均未触发，则失败
5. 如果触发了 1.1、1.2 或 3，则从 1 开始重复。

示例:

输入:(f, 2), (g, 2), (b, 1), (i, 2), (c, 1), (a, 0)

由于 (a, 0) 是根，我们要么按顺序执行，要么按后序执行。

然后我们生成 2 个子树:

in-order        post-order
    .                .
   /                /
  .                .
 /                /
f                f

(.表示空节点)

当我们得到 (g, 2) 时，我们已经可以丢弃有序树，因为我们不能从 f 的父级向右或向上，因为它是空的，所以我们被卡住了。

然后我们继续后序:

    .
   /
  .
 / \
f   g


    .
   /
  b
 / \
f   g


     .
   /   \
  b     .
 / \   /
f   g i


     .
   /   \
  b     c
 / \   /
f   g i


     a
   /   \
  b     c
 / \   /
f   g i