中序遍历和前序遍历重建二叉树

中序遍历

  在二叉树中，中序遍历是一种很常见的遍历方式，首先遍历左子树，然后根节点，最后右子树。

前序遍历

  前序遍历是先遍历根节点，然后左子树，最后右子树。

重建二叉树思想

  我们知道，前序遍历的第一个数字就是根节点，由根节点的值我们在中序遍历的序列中可以根据根节点的值区分出左子树还有右子树，以及每个子树的结点的数目，然后我们由此在前序遍历的序列中划分出相应的左右子树，进行递归进行。

代码实现

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int x) {
		val = x;
	}
}
public class Solution {
	//重建二叉树
	 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		 if(pre==null||in==null) {
			 return null;
		 }
		 //进入递归函数
		 return reConstructTree(pre,0,pre.length-1,in,0,in.length-1);
		 
	 }
	 
	public TreeNode reConstructTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
		//判断是否结束递归
		if(startPre>endPre|startIn>endIn) {
			return null;
		}
		int rootValue = pre[0];
		TreeNode root=new TreeNode(rootValue);
		root.left=null;
		root.right=null;
		int indexIn=0;
		//在中序遍历序列中找到根节点的位置
		for(int i=startIn;i<=endIn;i++) {
			if(in[i]==rootValue) {
				indexIn=i;
				break;
			}
		}
		//左子树的结点个数
		int leftLength= indexIn-startIn;
		int leftPreEnd=startPre+leftLength;
		//递归左右子树
		root.left=reConstructTree(pre,startPre+1,leftPreEnd,in,startIn,indexIn-1);
		root.right=reConstructTree(pre,leftPreEnd+1,endPre,in,indexIn+1,endIn);
		return root;
	}