一、问题引出
二叉树是一种特殊的树，它的每一个结点最多只有左右两棵子树，那么假设我们给定一个二叉树的结点值的遍历结果，如何恢复出树的结构呢？举个最简单的例子，假设给定一个二叉树的前序遍历结果为ABC，现在要根据遍历结果把二叉树恢复出来，那么能得到唯一一棵二叉树吗？显然是不行的，前序遍历是指先访问根结点，再访问左子树，最后访问右子树，那么以下五种情况都符合前序遍历结果ABC。因此，有必要探讨如何唯一确定一棵二叉树。
二、算法介绍
常用的确定一棵二叉树的算法有两种，第一种是使用两种遍历（前序+中序、后序+中序），第二种是#号法。
- 两种遍历确定一棵二叉树：（必须要有中序遍历）
- 前序遍历+中序遍历确定一棵二叉树；
- 中序遍历+后序遍历确定一棵二叉树；
- #号法确定一棵二叉树：如果没有左右子树，则使用#号代替，遍历时用#代替NULL。
下面分别对两种方法进行详细分析。
1. 中序遍历+前/后序遍历确定一棵二叉树
1.1 算法思想分析
通过上面的介绍可以看到，使用两种遍历来确定一棵二叉树的时候一定要有中序遍历。其实，这和三种遍历的自身特点是有关系的，前序遍历的顺序是先根结点，然后左子树，最后右子树，所以根结点一定在遍历结果的第一个位置上；后序遍历的顺序是，先左子树，然后右子树，最后根结点，所以根结点一定是在遍历结果的最后一个位置上。通过前序遍历和后序遍历可以确定出根结点。中序遍历的顺序是，先左子树，然后根结点，最后右子树，在遍历结果中，左右子树分别在根结点的两侧，这样就可以把左右子树区分开。可以看出，前/后序遍历和中序遍历的作用分别是：
- 前序遍历或后序遍历用于确定根节点；
- 中序遍历用于区分左右子树；
通过两种遍历，找出了根结点，并区分开了左右子树，这样就可以确定一棵二叉树了，下面以前序遍历加中序遍历为例，一步步分析如何通过前序遍历结果和中序遍历结果来恢复一棵二叉树（后续+中序遍历的方法与之类似，此文不再分析）。
1.2 算法流程
首先给出两个序列
前序遍历结果：A B C D E F G
中序遍历结果：C D B A F E G
| 第一步：确定整棵树的根结点及左右子树 |
|
根据分析，可以画出分析后的结果
这样就把问题分解为{C, D, B}和{F, E, G}两个子问题，首先分析左子树
| 第二步：分析左子树 |
|
继续画出示意图
分析{C，D}子序列
| 第三步：继续分析左子树的左子树（B结点的左子树） |
|
继续画出示意图
至此，整棵二叉树的左子树分析完毕，再用第二、三步同样的方法分析右子树{F，E，G}。
| 第四步：分析右子树 |
|
画出示意图
整棵二叉树分析完毕，并恢复出唯一的一棵二叉树，我们对该二叉树示意图进行前序遍历和中序遍历，结果分别为A B C D E F G和C D B A F E G，与题目中给的前序遍历序列和中序遍历序列一致，证明我们恢复得到树是正确的。
2. 号法确定一棵二叉树
2.1 算法思想分析
#号法确定一棵树的思想是，如果一个结点没有左右子树，也就是说如果左子树或右子树为NULL，就用一个#号代替，在遍历时给出带有#的遍历结果，既然没有左右子树就用一个#代替，那么连续两个#号前的结点一定是叶子结点，也就能确定一棵子树的结束，这样通过一种遍历的结点序列就能唯一确定一棵二叉树。
2.2 算法流程
首先给出一个#号法前序遍历的结点序列
前序遍历：ABC#D###EF##G##
| 具体步骤： |
|
三、结论
唯一确定一棵树的关键就在于寻找根结点和划分左右子树，不管是前序加中序遍历的方法还是#号法前序遍历的方法，都是在寻找根节点，划分左右子树的一个过程。
