题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 int now; 12 public void work(int []index, int []pre, int l, int r, TreeNode p) { 13 p.val = pre[now++]; 14 15 if (now < pre.length && index[pre[now]] >= l && index[pre[now]] <= r && 16 index[pre[now]] < index[p.val]) { 17 p.left = new TreeNode(0); 18 work(index, pre, l, index[p.val] - 1, p.left); 19 20 } 21 if (now < pre.length && index[pre[now]] >= l && index[pre[now]] <= r && 22 index[pre[now]] > index[p.val]) { 23 p.right = new TreeNode(0); 24 work(index, pre, index[p.val] + 1, r, p.right); 25 } 26 } 27 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 28 now = 0; 29 int Max = 0; 30 for (int i = 0; i < pre.length; ++i) { 31 Max = Math.max(pre[i], Max); 32 } 33 int []index = new int [Max + 1]; 34 for (int i = 0; i < in.length; ++i) { 35 index[ in[i] ] = i; 36 } 37 TreeNode p = new TreeNode(0); 38 work(index, pre, 0, pre.length - 1, p); 39 return p; 40 } 41 }