/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.*; public class Solution { Map<Integer,Integer> m = new HashMap<>(); public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { if(pre == null || pre.length == 0) return null; for(int i = 0; i < vin.length; i++){ m.put(vin[i], i); } return BuildTree(pre, vin, 0, pre.length - 1, 0, vin.length - 1); } public TreeNode BuildTree(int [] pre, int [] vin, int pStart, int pEnd, int inStart, int inEnd){ if(pStart > pEnd || inStart > inEnd) return null; int rootVal = pre[pStart]; int rootInIndex = m.get(rootVal); int leftSize = rootInIndex - inStart; TreeNode root = new TreeNode(rootVal); root.left = BuildTree(pre, vin, pStart + 1, pStart + leftSize, inStart, rootInIndex - 1); root.right = BuildTree(pre, vin, pStart + leftSize + 1, pEnd, rootInIndex + 1, inEnd); return root; } }