重建二叉树（Java）

大家好，又见面了，我是你们的朋友全栈君。

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。例如输入前序遍历序列{1， 2， 4， 7， 3， 5， 6， 8}和中序遍历序列{4， 7， 2， 1，5， 3， 8， 6}，则重建出二叉树并输出它的头结点。二叉树结点的定义如下：

struct BinaryTreeNode{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
}

知识点：

树：除了根结点之外每个结点只有一个父结点，根结点没有父结点；除了叶结点之外所有结点都有一个或多个子结点，叶结点没有子结点。父结点和子结点之间用指针链接。

二叉树：二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。在二叉树中最重要的操作是遍历，即按照某一顺序访问树中的所有结点。树的遍历方式：

前序遍历：先访问根节点，再访问左子结点，最后访问右子结点；（根左右）

中序遍历：先访问左子结点，再访问根结点，最后访问右子结点；（左根右）

后序遍历：先访问左子结点，再访问右子结点，最后访问根结点；（左右根）

前序遍历、中序遍历、后序遍历都可以用递归和循环进行实现。故树的遍历有3种方式6种实现。

宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点……一直到访问到最下面的一层结点。在同一层结点中，以从左到右的顺序依次访问。

二叉搜索树：左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。（二叉搜索树的搜索时间可以平均在O（logn）的时间内）。

二叉树的特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。红黑树是把树中的结点定义为红、黑两种颜色，并通过规则确保从根结点到叶结点的最长路径的长度不超过最短路径的两倍。

解题思路：

题目中给了我们先序遍历和中序遍历；在二叉树的前序遍历中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

题目给出的前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历的特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

由于在中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样就在前序和中序遍历的两个序列中，分别找到了左右子树对应的子序列。

我们已经分别找到了左右子树的前序和中序遍历，我们可以用同样的方法分别去构建左右子树，即递归实现。

定义二叉树结构：

public class TreeNode {
        //数据域
	public int data; 
	//左指针域
	public TreeNode left;
	//右指针域
	public TreeNode right;
        //构造带有参数的构造方法
	public TreeNode(int data) {
		this.data = data;
	}
        //重写toString方法
	public String toString() {
		return "TreeNode [data=" + data + ", left=" + left + ", right=" + right
				+ "]";
	}
}

前序和中序重建二叉树的代码：

public TreeNode rebuildBinaryTree(int preorder[], int inorder[]) {
	if (preorder == null || inorder == null) { //如果前序或者中序有一个是空直接返回
		return null;
	}
               // 定义构建二叉树的核心算法
	TreeNode root = rebuildBinaryTreeCore(preorder, 0, preorder.length - 1,
			inorder, 0, inorder.length - 1);
	return root;
}
// 构建二叉树的核心算法
public TreeNode rebuildBinaryTreeCore(int preorder[], int startPreorder,
		int endPreorder, int inorder[], int startInorder, int endInorder) {
	if (startPreorder > endPreorder || startInorder > endInorder) { //停止递归的条件
		return null;
	}
	TreeNode root = new TreeNode(preorder[startPreorder]);
	for (int i = startInorder; i <= endInorder; i++) {
		if (preorder[startPreorder] == inorder[i]) {
			// 其中（i - startInorder）为中序排序中左子树结点的个数
			//左子树
			root.left = rebuildBinaryTreeCore(preorder, startPreorder + 1,
					startPreorder + (i - startInorder), inorder,
					startInorder, i - 1);
			//右子树
			root.right = rebuildBinaryTreeCore(preorder, (i - startInorder)
					+ startPreorder + 1, endPreorder, inorder, i + 1,
					endInorder);

		}
	}
	return root;
}

/*
	4,7,3数量为3个即i-startInorder
 1    2 4 7        3 5 6 8
      4 7 2    1   5 3 8 6

             1
         2       3
      4        5   6
         7   8
*/

测试方法：

public static void main(String[] args) {
	int preorder[] = {1, 2, 4, 7, 3, 5, 6, 8};
	int inorder[] = {4, 7, 2, 1, 5, 3, 8, 6};
	TreeNode treeNode = rebuildBinaryTree(preorder, inorder);
	System.out.println(treeNode);
}

举一反三：

类似的由中序和后序构建二叉树和有前序和中序构建二叉树的思想是类似的。重建二叉树可以有前序和中序推导出来，也可以由中序和后序推导出来。这里实现由中序和后序重建二叉树。

有中序和后序重建二叉树代码：

public static TreeNode rebuildBinaryTree(int[] postorder, int[] inorder) {
	if (postorder == null || inorder == null) {
		return null;
	}
	TreeNode root = rebuildBinaryTreeCore(postorder, 0,
			postorder.length - 1, inorder, 0, inorder.length - 1);
	return root;
}

public static TreeNode rebuildBinaryTreeCore(int[] postorder,
		int startPostorder, int endPostorder, int[] inorder,
		int startInorder, int endInorder) {

	if (startPostorder > endPostorder || startInorder > endInorder) { // 终止递归的条件
		return null;
	}
	TreeNode root = new TreeNode(postorder[endPostorder]);
	for (int i = startInorder; i <= endInorder; i++) {
		if (inorder[i] == postorder[endPostorder]) {
			root.left = rebuildBinaryTreeCore(postorder, startPostorder,
					startPostorder - 1 + (i - startInorder), inorder,
					startInorder, i - 1);
			root.right = rebuildBinaryTreeCore(postorder, startPostorder
					+ (i - startInorder), endPostorder - 1, inorder, i + 1,
					endInorder);
		}
	}
	return root;
}

/*
 *  后序：2  4  3  1          6    7    5
 *  中序：1  2  3  4     5    6    7
 *             5     
 *       1           7
 *           3     6  
 *         2   4   
 */

测试：

public static void main(String[] args) {
	int []inorder = {1, 2, 3, 4, 5, 6, 7};
	int []postorder = {2, 4, 3, 1, 6, 7, 5};
	TreeNode treeNode = rebuildBinaryTree(postorder, inorder);
	System.out.println(treeNode);
}

小思：

这道编程考查对二叉树的遍历的理解程度，只有掌握了二叉树的三种遍历，才可以推导出二叉树的结构；

这道题它的经典之处在于递归，在每次递归时它的经典是把一颗完整的二叉树，分成了左子树、根、右子树，再在每个左右子树中再分，即把大问题转化为局部小问题，最后解决问题。值得学习，递归精髓。