algorithm - 前序到后序遍历

Question

如果二叉搜索树的前序遍历为6,2,1,4,3,7,10,9,11，如何求后序遍历？

Answer 1

给定树的先序遍历，它是通过执行以下操作构造的:输出，向左遍历，向右遍历。

由于后序遍历来自于BST，所以可以通过对数字进行排序，从后序遍历推导出中序遍历(向左遍历，输出，向右遍历)。在你的例子中，中序遍历是 1, 2, 3, 4, 6, 7, 9, 10, 11。

从两次遍历我们可以构建原始树。让我们为此使用一个更简单的示例:

• 预订:2、1、4、3
• 按顺序:1、2、3、4

前序遍历告诉我们树的根为 2。中序遍历告诉我们 1 落入左子树，3、4 落入右子树。左子树的结构很简单，因为它只包含一个元素。右子树的前序遍历是根据原来的先序遍历，取本子树中元素的顺序:4, 3，由此得知右子树的根为4，从中序遍历(3, 4)我们知道3落入了左子树。我们最终的树看起来像这样:

  2
 / \
1   4
   /
  3

有了树结构，我们就可以通过遍历树得到后序遍历:向左遍历，向右遍历，输出。本例后序遍历为1,3,4,2。

推广算法:

1. 前序遍历的第一个元素是树的根。小于根的元素构成左子树。大于根的元素构成右子树。
2. 使用第 1 步找到左右子树的结构，先序遍历由我们算出的元素组成，这些元素按照它们在原始预序中出现的顺序放置在该子树中遍历。
3. 后序遍历生成的树以获得与给定的前序遍历关联的后序遍历。

使用上述算法，问题中与前序遍历相关联的后序遍历为:1,3,4,2,9,11,10,7,6。到达那里留作练习.