由前序和中序构造二叉树
题目
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3

/ 

9  20

/  

15   7
理解
从前序中可以直接找到根节点，然后从中序中找到这个根节点并记录它的下标，这样在中序中，这个结点的左边的数都是它左子树上的，它的右边的数都是它右子树上的，然后从前序序列中遍历到下标的长度，这段期间的数字就是新的一个前序序列，继续第一个是根节点，重复上面的过程。同理，右子树也是一样的。
代码
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    //前序序列为空
       if(preorder.length==0)
           return null;
          //根节点
        int p=preorder[0];
        int q; 
        //找到中序中相同结点的下标
        for(q=0;q<inorder.length;q++){
            if(p==inorder[q])
                break;
        }
        //创建新的根节点
        TreeNode root=new TreeNode(p);
        //左子树的前序序列
        int[]m1=Arrays.copyOfRange(preorder,1,q+1);
        //左子树的中序序列
        int[]m2=Arrays.copyOfRange(inorder,0,q);
        root.left=buildTree(m1,m2);
        //右子树的前序序列
        int[]n1=Arrays.copyOfRange(preorder,q+1,preorder.length);
        //右子树的中序序列
        int[]n2=Arrays.copyOfRange(inorder,q+1,inorder.length);
        root.right=buildTree(n1,n2);
        return root;
    }
}

由中序和后续构造二叉树
题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:

你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：
3

/ 

9  20

/  

15   7
理解
后续的最后一个结点是根节点，然后从中序中找到这个结点并记录它的下标，然后中序中它的左边数字就是它的左子树，后续中从前往后遍历到下标的长度，形成新的后序序列，它的最后一个数就是它的根节点，然后和前面那道题同理。
代码
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length==0)
            return null;
        int a=postorder[postorder.length-1];//后续的最后一个结点是根节点
        int b;
        for(b=0;b<inorder.length;b++){
            if(inorder[b]==a)
                break;//找到根节点在中序的下标
        }
        TreeNode root=new TreeNode(a);
        int []m1=Arrays.copyOfRange(inorder,0,b);//左子树的中序序列
        int[]m2=Arrays.copyOfRange(postorder,0,b);//左子树的后序序列
        root.left=buildTree(m1,m2);
        int[]n1=Arrays.copyOfRange(inorder,b+1,inorder.length);
        int[]n2=Arrays.copyOfRange(postorder,b,postorder.length-1);
        root.right=buildTree(n1,n2);
        return root;
    }
}

注意：不能由前序和后续构造二叉树，因为这两个只能找到根节点，左右子树不唯一。

下面三种序列可以唯一的构造唯一的一棵二叉树：

前序序列和中序序列构造二叉树  

后序序列和中序序列构造二叉树

层次遍历序列和中序遍历序列构造二叉树  

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MaxSize 10
typedef struct BTNode{
	char data;
	struct BTNode *lchild,*rchild;
}BTNode,*BiTree;

//根据前序序列，中序序列建造一棵二叉树
//参数含义：pre[]前序序列  in[]中序序列
//			L1  R1用于指定pre[]的搜索区域
//			L2  R2用于指定in[]的搜索区域 
BiTree createBiTree(char pre[],char in[],int L1,int R1,int L2,int R2){
	if(L1>R1){
		return NULL;//递归出口 
	}
	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
	s->lchild =NULL;
	s->rchild =NULL;
	s->data=pre[L1];
	int i;
	//根据中序序列的特性，元素左边的元素属于该节点的左孩子序列，右边则是右孩子序列 
	for(i=L2;i<=R2;i++){
		if(pre[L1]==in[i]) break;//在中序序列找到该元素 
	}
	s->lchild=createBiTree(pre,in,L1+1,L1+i-L2,L2,i-1);//递归 
	s->rchild=createBiTree(pre,in,L1+i-L2+1,R1,i+1,R2); 
	
	return s;
}
//根据后序中序建立二叉树 
BiTree createBiTree2(char post[],char in[],int L1,int R1,int L2,int R2){
	if(L1>R1){
		return NULL;//递归出口 
	}
	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
	s->lchild =NULL;
	s->rchild =NULL;                   
	s->data=post[R1];//后序序列最后一个节点为根节点 
	int i;
	//根据中序序列的特性，元素左边的元素属于该节点的左孩子序列，右边则是右孩子序列 
	for(i=L2;i<=R2;i++){
		if(post[R1]==in[i]) break;//在中序序列找到该元素 
	}
	//递归 面试官：为什么要减去L2? 答：递归传下去的是整个数组，需要根据参数找到递归出口,-L2是缩小查找范围 
	s->lchild=createBiTree2(post,in,L1,L1+i-L2-1,L2,i-1);
	s->rchild=createBiTree2(post,in,L1+i-L2,R1-1,i+1,R2); 
	
	return s;
}
//该函数用于在中序序列中找到key,返回其位置 
//参数含义：in[]：中序序列  key:所要查找元素 L,R:查找范围 
int serach(char in[],char key,int L,int R){
	for(int i=L;i<=R;i++){
		if(in[i]==key) return i;
	}
	return -1;
}

//因为在中序序列元素的左面的元素在层次遍历序列中并不连续，所以需要用子序列函数将并不连续的序列连续起来
//为什么要连续起来？因为需要连续起来才能和中序序列构造出二叉树
//思路：在中序序列里查找到一个范围，从这个范围里遍历元素，在层次遍历序列里找该元素 
//参数含义：sublevel[]：存放子序列数组  level[]：层次遍历序列  in[]:中序序列 n:level层次序列长度 L,R:查找范围 
void getSubLevel(char sublevel[],char level[],char in[],int n,int L,int R){
	int k=0;
	for(int i=0;i<n;i++){
		if(serach(in,level[i],L,R)!=-1)
		   sublevel[k++]=level[i]; 
	}
}
//由中序序列和层次遍历序列构造二叉树 
BiTree createBiTree3(char level[],char in[],int n,int L,int R){
	if(L>R) return NULL;
	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
	s->lchild =NULL;
	s->rchild =NULL;                   
	s->data=level[0];
	int i=serach(in,level[0],L,R);
	//找到i便可以确定左右子树答大小 
	int LN=i-L; char LLevel[LN];
	int RN=R-i; char RLevel[RN];
	getSubLevel(LLevel,level,in,n,L,i-1);//得到子序列 
	getSubLevel(RLevel,level,in,n,i+1,R);
	
	s->lchild=createBiTree3(LLevel,in,LN,L,i-1);//用子序列递归 
	s->rchild=createBiTree3(RLevel,in,RN,i+1,R); 
	return s;
}
void visit(BiTree T) {
	printf("%c  ",T->data);
}
//前序遍历 
void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);//根 
		PreOrder(T->lchild);//左 
		PreOrder(T->rchild);//右 
	}
} 
//中序遍历 
void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}
//后序遍历 
void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
} 
//层次遍历 
void level(BiTree T){
	if(T!=NULL){
		int front=0;
		int rear=0;
		BiTree queue[MaxSize];
		BiTree p;
		p=T;
		rear=(rear+1)%MaxSize;
		queue[rear]=p;
		while(rear!=front){
			front=(front+1)%MaxSize;
			p=queue[front];
			visit(p); 
			if(p->lchild!=NULL){
				rear=(rear+1)%MaxSize;
				queue[rear]=p->lchild; 
			} 
			if(p->rchild!=NULL){
				rear=(rear+1)%MaxSize;
				queue[rear]=p->rchild;
			}
			
		}
	}
}
int main(){
	char c[]="ABDECFGH";//前序序列 
	char d[]="DBEACGFH";//中序序列 
	char p[]="DEBGHFCA";//后序序列 
	char l[]="ABCDEFGH";//层次遍历序列 
	BTNode *r=createBiTree(c,d,0,7,0,7);
	BTNode *r2=createBiTree2(p,d,0,7,0,7);
	BTNode *r3=createBiTree3(l,d,8,0,7); 
	printf("前序序列为："); 
	PreOrder(r);
	printf("\n");
	printf("后序序列为：");
	PostOrder(r2);
	printf("\n");
	printf("中序序列为："); 
	InOrder(r3);
	printf("\n");
	printf("层次遍历为：");
    level(r3); 
	printf("\n");
	
} 

代码运行截图：

文章目录
从前序与中序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树


遇到二叉树相关的问题，多半和递归有关系，二叉树遍历也是递归遍历（从树得到序列），二叉树的构建也是递归构建（从序列得到一个二叉树）


依靠前序遍历数组和中序遍历数组可以唯一确定一棵二叉树；

依靠中序遍历数组和后序遍历数组可以唯一确定一棵二叉树；

但是，依靠前序遍历数组和后序遍历数组无法唯一确定一棵二叉树；

从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。当然也是力扣105的原题。
注意:你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

分析：
给定一个前序序列和一个中序序列，且里面没有重复的元素，如何构造一和二叉树呢？我们可以先单独观察两个序列的特征：
前序遍历：遍历规则为(根，[左侧区域]，[右侧区域])。

中序遍历：遍历规则为([左侧区域]，根，[右侧区域])。
其中前序遍历的左侧区域和中序遍历的左侧区域包含元素的范围相同，根也是相同的。所以可以进行这样的操作：

根据前序遍历的第一个找到根节点，可以确定根。
通过中序遍历找到根节点的值，这样可以知道左侧区域和右侧区域节点个数多少。
根节点左侧区域由前中序列确定的左侧区域确定，根节点的右侧节点由前中序序列的右侧区域确定。

具体的实现上，可以使用一个HashMap存储中序存储的序列，避免重复计算。实现的代码为：
/**
 * Definition for a binary tree node.
 * public class TreeNode {   // leecode给你提供一个二叉树类给你用
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
		if(preorder.length==0)
			return null;
		TreeNode root=new TreeNode(preorder[0]);
		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
		for(int i=0;i<inorder.length;i++)
		{
// 为什么要把中序遍历的整个数组放到map中，
// 因为前序序列中确定的根节点要在中序序列中确定位置，
// 然后确定左右子树，所以需要将数组变为map,
			map.put(inorder[i], i);
		}
		// 六个参数，preorder三个，inorder三个
		return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
    }

	private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {		
		if(preEnd<preStart||inEnd<inStart)
			return null;
		TreeNode node=new TreeNode(preorder[preStart]);  // 拿着前序遍历数组的第一个元素，新建一个二叉树根结点，这个根节点是作为返回值的
		int i=map.get(preorder[preStart]);// 每次前序序列确定的根节点在中序遍历中的位置i，然后分割左右子树
		
		int leftlen=i-inStart;// i-inStart变为中序遍历左边的长度，即左子树长度
		//六个参数，前序遍历三个，中序遍历三个，继续构造左子树
		node.left=buildTree(preorder, preStart+1, preStart+leftlen, map, inStart, i-1);
		//六个参数，前序遍历三个，中序遍历三个，继续构造右子树
		node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);
		return node;		
	}
}

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

解释左子树：node.left=buildTree(preorder, preStart+1, preStart+1+leftlen, map, inStart, i-1);

之前是 		return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
前序序列启始点：为什么之前是preStart=0，现在是preStart+1？因为去掉一个根节点，good
前序序列终点：为什么之前是preorder.length-1，现在是preStart+leftlen？因为之前是整个前序序列，现在是左子树，整个前序序列是preorder[0 到 preorder.length-1]，左子树是preorder[preStart+1，(preStart+1)+(leftlen-1)]变为preorder[preStart+1，preStart+leftlen]，leftlen是每次更新的，表示左子树长度，用中序序列算出来的，good
中序序列启始点：为什么之前是inStart=0，现在还是inStart？因为中序遍历的左子树本来就在左边，从最左边开始没问题，good
中序序列终点：为什么之前右子树终点是inorder.length-1,现在是i-1？因为根节点是i，所有中序遍历的左子树终点是i-1，good
返回值：为什么返回值node.left？因为子树的根节点node就是母树的左子树根节点node.left.
解释右子树：node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);

之前是 		return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
前序序列启始点：为什么之前是preStart=0，现在是preStart+leftlen+1？之前是整个树，现在是右子树，右子树根节点从 preStart+leftlen+1 开始。
前序序列终点：为什么之前是preorder.length-1，现在是preEnd(即还是preorder.length-1)？对于前序

序列（中左右）来说，根节点在最前面，整个树的结束和右子树的结束是一样的。
中序序列启始点：为什么之前是inStart=0，现在还是i+1？因为之前的整个树，所以中序遍历从下标0开始，现在是右子树，刚才算出根节点在中序序列的下标识i，所以右子树中，中序序列从(i+1)开始。
中序序列终点：为什么之前右子树终点是inorder.length-1,现在是inEnd(即还是inorder.length-1)？对于中序序列（左中右）来说，根节点在中间，整个树的结束和右子树的结束是一样的。
返回值：为什么返回值node.right？因为对于右子树来说，子树的根节点node就是母树的左子树根节点node.right.

关于中序序列从数组变为map，为什么新得到的map，key存放数组元素，value存放数组下标？

这是由map这个数据结构从查找性质决定的，在map中，根据key可以找到唯一确定的value，但是通过value无法找到唯一确定的key，每次通过前序序列确定根节点后，要通过中序序列确定根节点的位置，所有只能下标放value，元素放在key。


为什么buildTree()方法最后返回来一个node?

这个node是整个树的根节点，将整个树构建完成后返回这个根节点，为什么呢？因为只有从这个根节点，就可以遍历整颗树（无论是前序遍历、中序遍历还是后序遍历），所以返回了整个树的根节点就相当于返回了整个二叉树。

从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树，力扣106题
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

分析：

有了上面的分析，那么通过一个后序遍历和中序遍历去构造一棵二叉树，其实原理和前面的也是一样的。
中序遍历：遍历规则为([左侧区域]，根，[右侧区域])。

后序遍历：遍历规则为([左侧区域]，[右侧区域]，根)。
具体实现的代码为：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public TreeNode buildTree(int[] inorder,int[] postorder) {
		if(postorder.length==0)
			return null;
		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
		for(int i=0;i<inorder.length;i++)
		{
			map.put(inorder[i], i);  // 中序序列从数组变为map
		}
		//六个参数，前三个参数是后序序列，后三个参数是中序序列
		return buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
    }

	private TreeNode buildTree(int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
		if(postEnd<postStart||inEnd<inStart)
			return null;
		TreeNode node=new TreeNode(postorder[postEnd]);
		int i=map.get(postorder[postEnd]);
			
		int leftlen=i-inStart;
		
		node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);
		node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);           return node;		
	}
}

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7


如果理解了leetcode105，这个就很容易理解了，没必要写了，还是写一下吧

解释左子树：node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);

之前是 		buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
后序序列启始点：为什么之前是preStart=0，现在还是0？因为后序序列（左右中），母树的最左节点也就是左子树的最左节点。
后序序列终点：为什么之前是preorder.length-1，现在是preStart+leftlen-1？之前是母树是后序序列，现在是母树的左子树的后序序列，对于母树的左子树的后序序列，由于长度为leftlen，所以最后一个节点就是 preStart+leftlen-1 。
中序序列启始点：为什么之前是inStart=0，现在还是inStart？对于中序序列（左中右），母树的最左节点也就是左子树的最左节点。
中序序列终点：为什么之前右子树终点是inorder.length-1,现在是i-1？对于中序序列（左中右），由于确定了根节点所在下标是i，所有左子树最后节点就是i-1。
返回值：为什么返回值node.left？因为子树的根节点node就是母树的左子树根节点node.left.
解释右子树：node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);

之前是 		buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
后序序列启始点：为什么之前是preStart=0，现在是preStart+leftlen？现在是右子树，对于后序序列来说（左右中），右子树的开始节点就是，左子树开始节点postStart + 左子树长度leftlen，所以就是preStart+leftlen。
后序序列终点：为什么之前是preorder.length-1，现在是preEnd-1(即还是preorder.length-2)？现在是遍历右子树，对于后序序列来说，最后一个是母树的根节点，所有要去掉，所以就是preEnd-1了。
中序序列启始点：为什么之前是inStart=0，现在还是i+1？对于中序序列（左中右），由于确定了根节点所在下标是i，所以右子树最后节点就是i+1。
中序序列终点：为什么之前右子树终点是inorder.length-1,现在是inEnd(即还是inorder.length-1)？对于中序序列（左中右），母树最右端也就是右子树最右端，所以是一样的。
返回值：为什么返回值node.right？因为对于右子树来说，子树的根节点node就是母树的左子树根节点node.right.

文章目录
题目
解题思路
根据中序、后序构造树
根据中序、前序构造树
前序，后序构造树
中序存在与否对树的构建有什么影响

题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:

你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7
后序遍历 postorder = [9,15,7,20,3]

解题思路
中序可以和前序、后序、层序的任意一个搭配来构建唯一的二叉树。

若没有中序，其他的序列搭配都无法构建唯一的二叉树，因为先序、后序、层序都用于提供根结点，只有中序才能区分左右子树。
根据中序、后序构造树
class Solution {
    private int[] post; //后序序列
    private Map<Integer, Integer> map; //哈希表记录结点值在中序里的下标

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder;
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return helper(0, inorder.length - 1, post.length - 1);
    }

    /**
     * 根据中序始末下标构建树
     * @param begin 中序的起始下标
     * @param end 中序的结束下标
     * @param postidx 根结点在后序里的下标
     * @return 返回树的根结点
     */
    private TreeNode helper(int begin, int end, int postidx) {
        if(begin > end)    return null; //没有结点，返回空树
        int rootidx = map.get(post[postidx]); //根结点在中序里的下标，用于区分左右子树
        TreeNode root = new TreeNode(post[postidx]);
        int rightcnt = end - rootidx; //右子树结点数
        root.left = helper(begin, rootidx - 1, postidx - rightcnt - 1); //根据子树的中序构建子树
        root.right = helper(rootidx + 1, end, postidx - 1);
        return root;
    }
}

根据中序、前序构造树
class Solution {
    private int[] pre; //前序
    private Map<Integer, Integer> map; //哈希表用于记录结点值在中序里的下标

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pre = preorder;
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return helper(0, inorder.length - 1, 0);
    }

    /**
     * 根据中序始末下标构建树
     * @param begin 中序起始下标
     * @param end 中序结束下标
     * @param preidx 根结点在前序里的下标
     * @return 返回树的根结点
     */
    private TreeNode helper(int begin, int end, int preidx) {
        if(begin > end)    return null; //没有结点，返回空树
        int rootidx = map.get(pre[preidx]); //根据根结点在前序里的下标求出根节点值后查询其在中序里的下标，用于区分左右子树
        TreeNode root = new TreeNode(pre[preidx]);
        root.left = helper(begin, rootidx - 1, preidx + 1); //根据子树中序构建子树
        int leftcnt = rootidx - begin; //左子树结点数
        root.right = helper(rootidx + 1, end, preidx + leftcnt + 1);
        return root;
    }
}

前序，后序构造树


如果遍历这个左子树

前序遍历的结果是[2,4,5]

后序遍历的结果是[4,5,2]
我们根据2就可以确定出后序遍历的左子树范围

因为后序遍历的整棵树的结果是[4,5,2,6,7,3,1]

现在我们找到2了，根节点的位置是固定出现在最后的，那么右子树的范围也就可以确定了。

后序遍历数组下标是从0开始的，我们确定了2的位置，还需要+1，这样就得到了整个左子树的个数。
class Solution {
    private int[] pre; //前序
    private Map<Integer, Integer> map; //记录结点值在后序中的下标
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.pre = pre;
        map = new HashMap<>();
        for(int i = 0; i < post.length; i++)
            map.put(post[i], i);
        return build(0, pre.length - 1, 0);
    }
    /**
     * 根据前序后序构建树
     * @param begin 前序的起点下标
     * @param end 前序的终点下标
     * @param postBegin 后序的起点下标
     * @return 返回构建的树
     */
    private TreeNode build(int begin, int end, int postBegin) {
        if(begin > end)    return null; //没有结点，返回空树
        TreeNode root = new TreeNode(pre[begin]); //前序第一个结点就是当前根结点
        if(begin < end) { //若还有子结点
            int leftv = pre[begin + 1]; //默认一定有左子树，左子树根结点下标即begin + 1
            int leftcnt = map.get(leftv) - postBegin + 1; //计算左子树结点数
            root.left = build(begin + 1, begin + leftcnt, postBegin); //递归构建子树
            root.right = build(begin + leftcnt + 1, end, postBegin + leftcnt);
        }
        return root;
    }
}

中序存在与否对树的构建有什么影响
建议先完全掌握这篇题解中的两段代码。

中序+前序/后序
关键在于理解：前序和后序都只用于提供根结点，只有中序才能区分左右子树。

因为有了中序序列，得到根结点在中序中的位置后，根结点左边的一定都是左子树结点，右边的一定都是右子树结点，这是由中序定义的左->中->右遍历顺序决定好了的。

所以我们可以严格区分出左右子树，递归地构建出唯一的二叉树。
值得注意的是，本题的前序+后序是不能构建唯一的二叉树的。
或许会有人说，前序+后序似乎也能构建唯一的二叉树。

其实不能，那么本题中的什么东西使人产生这种错觉呢。

考虑下面代码中的这一段：
int leftv = pre[begin + 1]; //默认一定有左子树，左子树根结点下标即begin + 1
int leftcnt = map.get(leftv) - postBegin + 1; //计算左子树结点数
root.left = build(begin + 1, begin + leftcnt, postBegin); //递归构建子树
root.right = build(begin + leftcnt + 1, end, postBegin + leftcnt);

一上来就求左子树根结点的值leftv，和左子树结点数leftcnt，但是并不考虑是否存在左子树。这样的做法认为只要有子结点，就默认有左子树，没有考虑到可能压根就不存在左子树，可能仅仅只有右子树。因此，前序+后序是不能构建出唯一的二叉树的。

参考：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/marvelzhong-deng-de-xue-xi-bi-ji-106-by-tyanyone-2/