7 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len=preorder.length;
return buildTreeCore(preorder, inorder, 0, len-1, 0, len-1);
}
private TreeNode buildTreeCore(int[] pre, int[] in, int preL, int preR, int inL, int inR){
if(preL>preR || inL>inR) return null;
int val=pre[preL];
TreeNode root=new TreeNode(val);
int inIndex=inL;
while(in[inIndex]!=val) inIndex++;
int leftPreR=preL+inIndex-inL;
root.left=buildTreeCore(pre, in, preL+1,leftPreR, inL, inIndex-1);
root.right=buildTreeCore(pre, in, leftPreR+1, preR, inIndex+1, inR);
return root;
}
}
描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：
{1,2,5,3,4,6,7}
这题很难。。
前序遍历到一个值，这个值在中序遍历的位置的左边是这个是的左子树部分，右边是右子树部分。
例如前序遍历 {1,2,4,7,3,5,6,8} 和中序遍历 {4,7,2,1,5,3,8,6} 。前序遍历的第一个值 1 把中序遍历分为2部分， 4，7，2 是 1 的左子树，5，3，8，6 是 1 的右子树。前序遍历的第二个节点是 2 ，2 把刚才中序遍历分出来的左子树部分又分成2部分，4，7 是 2 的左子树，右子树没有节点。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return reConstruct(pre,in,0,pre.length-1,0,in.length-1);
}
private TreeNode reConstruct(int[] pre, int[] in, int preL, int preR, int inL, int inR){
if(preL>preR || inL>inR || preR>pre.length-1 || inR>in.length-1) return null;
int val=pre[preL];
TreeNode root=new TreeNode(val);
int count=0;
int index=inL;
while(in[index]!=val){
++index;
++count;
}
root.left=reConstruct(pre,in,preL+1,preL+count,inL,inL+count-1);
root.right=reConstruct(pre,in,preL+count+1,preR,inL+count+1,inR);
return root;
}
}