此博文主要讲述了构造二叉树的两种方法：
1、通过先序和中序构造出二叉树( 来自leetCode OJ上的 题目：Construct Binary Tree from Preorder and Inorder Traversal )
2、通过后序和中序构造出二叉树( 来自leetCode OJ上的 题目：Construct Binary Tree from Inorder and Postorder Traversal)
这两题的解法类似，下面我来详细讲下如何通过
二叉树的先序序列和中序序列来构造出二叉树，至于后序序列和中序序列就不着重讲了哈！
题目：
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题目要求我们通过中序序列和先序序列来构造出这棵二叉树，返回它的根节点。
那么我们先模拟随便画出一棵二叉树来，再把它的先序，中序，后序全部写出来
int[] preOrder = new int[]{7,-10,-4,3,-1,2,-8,11};
int[] pZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3RPcmRlciA9IG5ldyBpbnRbXXstNCwtMSwzLC0xMCwxMSwtOCwyLDd9Ozxicj4KaW50W10gaW5PcmRlciA9IG5ldyBpbnRbXXstNCwtMTAsMywtMSw3LDExLC04LDJ9Ozwvc3Ryb25nPjxicj4KPC9wPgo8cD48YnI+CjwvcD4KPHA+PHN0cm9uZz694sziy7zCt6O6PC9zdHJvbmc+PC9wPgo8cD7I58nPo6zO0sPHtcO1vcHL0ru/w7b+subK97XEz8jQ8tDywdBwcmVPcmRlciA9IHs3LC0xMCwtNCwzLC0xLDIsLTgsMTF9O7rN1tDQ8tDywdBpbk9yZGVyCiA9IHstNCwtMTAsMywtMSw3LDExLC04LDJ9OzwvcD4KPHA+ztLDx8/r0qq5ub2os/bV4r/Dtv6y5sr3o6zEx8O0ztKyydPDtd256bXEt723qMC0yLe2qLP2w7+49r3hteO6zb3hteO85LXEudjPtTwvcD4KPHA+zai5/c/I0PLQ8sHQezcsLTEwLC00LDMsLTEsMiwtOCwxMX2jrM7Sw8e/ydLU1qq1wKOstdrSu7j2veG14ze/z7aoyse2/rLmyve1xLj5veG146Ostvi12rb+uPa94bXjLTEwo6zT0L/JxNzKx7j5veG147XE1/PX08r3tcS4+b3hteOjrNKy09C/ycTcysfT0tfTyve1xLj5veG146Oovt/M5bXDv7TW0NDy0PLB0NbQtcQg"7" 左边是否还有其他的结点值，或者右边是否还有其他的结点值），居然这个大问题可以被分解成小问题，我们选择采用递归的方式来解决这个问题
1. 首先通过preOrder序列，得到根结点root！
2. 递归求出root的左子树
3. 递归求出root的右子树
4. 将左子树的根结点赋值给root.left, 右子树的根结点赋值给root.right
AC代码（Construct Binary Tree from Preorder and Inorder Traversal ）:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0)
return null;
int len = inorder.length;
return createTreeNode(preorder,inorder,0,len-1,0);
}
public TreeNode createTreeNode(int[] preorder, int[] inorder, int inLeft, int inRight, int preIndex){
//判断是否为叶子结点
if (inLeft == inRight){
TreeNode node = new TreeNode(inorder[inLeft]);
node.left = null;
node.right = null;
return node;
}
//把preOrder中当前下标preIndex指向的val取出
int val = preorder[preIndex];
int findIndex = inLeft;
//找到val在inOrder中的位置(该子树的根节点位置)
while (findIndex != inRight && val != inorder[findIndex]){
findIndex++;
}
TreeNode leftNode;
TreeNode rightNode;
//判断是否有左右子树，并创建出相应的左右子树（如果val在inOrder中的位置下标等于inLeft，表明这个子树是没有左子树的，而val在inOrder中的位置下标等于inRight，表明这个子树没有右子树）
if (findIndex == inLeft){
leftNode = null;
}else{
leftNode = createTreeNode(preorder,inorder,inLeft,findIndex-1,++preIndex);
}
if (findIndex == inRight){
rightNode = null;
}else{
rightNode = createTreeNode(preorder,inorder,findIndex+1,inRight,++preIndex);
}
//把左右子树赋值给root结点
TreeNode root = new TreeNode(val);
root.left = leftNode;
root.right = rightNode;
return root;
}
}AC代码（Construct Binary Tree from Inorder and Postorder Traversal)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int postIndex;
public TreeNode buildTree(int[]