输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}, 则重建二叉树并返回.
- /**
- * Definition for binary tree
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- import java.util.HashMap;
- import java.util.Map;
- public class Solution {
- private Map<Integer,Integer> map;
- public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
- map=new HashMap<Integer,Integer>();
- for(int i=0;i<in.length;i++){
- map.put(in[i],i);
- }
- return RecurConstructTree(pre,0,pre.length-1,0);
- }
- public TreeNode RecurConstructTree(int[] pre,int preL,int preR,int inL){
- if(preL>preR){
- return null;
- }
- TreeNode root=new TreeNode(pre[preL]);
- int index=map.get(root.val);
- int leftSize=index-inL;
- root.left=RecurConstructTree(pre,preL+1,preL+leftSize,inL);
- root.right=RecurConstructTree(pre,preL+leftSize+1,preR,inL+leftSize+1);
- return root;
- }
- }
来源: http://www.bubuko.com/infodetail-2902010.html