题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
import java.util.Arrays;
import java.util.*;
public class Solution {
static Map<Integer,Integer> map;
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0)return null;
map=new HashMap<Integer,Integer>();
int n=in.length;
for(int i=0;i<n;i++){
map.put(in[i],i);
}
TreeNode root=solveHelp(pre,0,n-1,in,0,n-1);
return root;
}
// 构建树
public static TreeNode solveHelp (int[] xianxu,int preLeft,int preRight,int[] zhongxu,int inLeft,int inRight) {
if(preLeft>preRight)return null;
int in_root=map.get(xianxu[preLeft]);
int left_nums=in_root-inLeft;
TreeNode root=new TreeNode(xianxu[preLeft]);
root.left=solveHelp(xianxu,preLeft+1,left_nums+preLeft,zhongxu,inLeft,in_root-1);
root.right=solveHelp(xianxu,left_nums+preLeft+1,preRight,zhongxu,in_root+1,inRight);
return root;
}
} 