题目
给定一棵树的前序与中序遍历，构成出这棵树
或者
给定一棵树的后序与中序遍历，构成出这棵树
解题方法
在Java二叉树相关知识中介绍过已知二叉树的前序、中序和后序遍历。
在讲解之前要明确知道只有前序（或者后序）与中序一起才可以唯一确定一棵二叉树。也就是说前序-中序和后序-中序可以确定二叉树，而前序-后序不可以确定二叉树。例如给定一个前序遍历为（2，1），后序遍历为（1，2），那么可能存在如下图的树构成
前序遍历为（2，1），后序遍历为（1，2）可能构成的二叉树
在这里，讲解给定一棵树的前序与中序遍历，构成出这棵树。
- 首先回想二叉树的中序与前序遍历的特点
前序遍历的第一个节点node1是树根
那么中序遍历node1在中序遍历结果中会把树拆分成两部分，前部分就是树的左子树，后半部就是树的右子树
- 除去node1节点，余下的前序遍历结果根据中序结果的拆分，同样会分成两部分，即前半部分的左子树和后半部分的右子树。这时左右子树分别又有了自己的前序和中序遍历
- 利用左右子树的前序和中序遍历递归实现求解
而给定一棵树的后序与中序遍历，与上述方法刚好相反，后序遍历的最后一个结点是树根。
代码
给定一棵树的前序与中序遍历，构成出这棵树
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
}
//递归实现
private TreeNode buildTreeHelper(int[] preorder, int[] inorder,
int preLeft, int preRight,
int inLeft, int inRight){
if(inLeft > inRight){//如果中序遍历的左起始点大于右起始点，则表明子树为空
return null;
}
if(inLeft == inRight){//如果中序遍历的左起始点等于右起始点，则子树只有一个节点直接返回即可
return new TreeNode(inorder[inLeft]);
}
int rootVal = preorder[preLeft];//前序遍历的第一个节点为树根
int inLocation = inLeft;
while(inLocation <= inRight){//循环找到树根在中序遍历的位置，将树拆分为左右子树两部分
if(inorder[inLocation] == rootVal){
break;
}
inLocation++;
}
TreeNode root = new TreeNode(rootVal);//生成树根节点
int leftSize = inLocation - inLeft;//确定左子树节点个数
int rightSize = inRight - inLocation;//确定右子树节点个数
root.left = buildTreeHelper(preorder, inorder,
preLeft+1, preLeft+leftSize,
inLeft, inLocation-1);//递归构造左子树
root.right = buildTreeHelper(preorder, inorder,
preLeft+leftSize+1, preLeft+leftSize+rightSize,
inLocation+1, inRight);//递归构造右子树
return root;
}
给定一棵树的后序与中序遍历，构成出这棵树
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTreeHelper(postorder, inorder, 0, postorder.length-1, 0, inorder.length-1);
}
//递归实现
private TreeNode buildTreeHelper(int[] postorder, int[] inorder,
int postLeft, int postRight,
int inLeft, int inRight){
if(inLeft > inRight){//如果中序遍历的左起始点大于右起始点，则表明子树为空
return null;
}
if(inLeft == inRight){//如果中序遍历的左起始点等于右起始点，则子树只有一个节点直接返回即可
return new TreeNode(inorder[inLeft]);
}
int rootVal = postorder[postRight];//后序遍历的最后一个节点是树根
int inLocation = inLeft;//循环找到树根在中序遍历的位置，将树拆分为左右子树两部分
while(inLocation <= inRight){
if(inorder[inLocation] == rootVal){
break;
}
inLocation++;
}
TreeNode root = new TreeNode(rootVal);//生成树根节点
int leftSize = inLocation - inLeft;//确定左子树节点个数
int rightSize = inRight - inLocation;//确定右子树节点个数
root.left = buildTreeHelper(postorder, inorder,
postLeft, postLeft+leftSize-1,
inLeft, inLocation-1);//递归构造左子树
root.right = buildTreeHelper(postorder, inorder,
postLeft+leftSize, postRight-1,
inLocation+1, inRight);//递归构造右子树
return root;
}
