博客

题目

二叉树的前序以及后续序列，以空格间隔每个元素，重构二叉树，最后输出二叉树的三种遍历方式的序列以验证。

输入：

1 2 3 4 5 6 7 8 9 10

3 2 5 4 1 7 8 6 10 9

输出：

1,2,3,4,5,6,7,8,9,10

3,2,5,4,1,7,8,6,10,9

3,5,4,2,8,7,10,9,6,1

分析

以上述输入为例，该树的结构为：

在解决这方面问题时，需要把控这几个因素：

(1)前序的第一个元素必为根节点；

(2)中序中在根节点左边的为左子树，在根节点右边的为右子树。

抓住上面两点，就可以无限递归，从而产生一个完整的二叉树。

算法演算

前序：1 2 3 4 5 6 7 8 9 10

中序：3 2 5 4 1 7 8 6 10 9

(1)第一次：

产生节点 1。

生成左子树

先序：2 3 4 5

中序：3 2 5 4

生成右子树

前序：6 7 8 9 10

中序：7 8 6 10 9

(2)第二次

产