1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 16, 2015
4+ Problem: Construct Binary Tree from Preorder and Inorder Traversal
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
7+ Notes:
8+ Given preorder and inorder traversal of a tree, construct the binary tree.
9+ Note:
10+ You may assume that duplicates do not exist in the tree.
11+
12+ Solution: Recursion.
13+ */
14+
15+ /**
16+ * Definition for binary tree
17+ * public class TreeNode {
18+ * int val;
19+ * TreeNode left;
20+ * TreeNode right;
21+ * TreeNode(int x) { val = x; }
22+ * }
23+ */
24+ public class Solution {
25+ public TreeNode buildTree (int []preorder ,int []inorder ) {
26+ if (inorder .length ==0 ||preorder .length ==0 ||inorder .length !=preorder .length )return null ;
27+ return buildTreeRe (preorder ,0 ,inorder ,0 ,preorder .length );
28+ }
29+ public TreeNode buildTreeRe (int []preorder ,int s1 ,int []inorder ,int s2 ,int size ) {
30+ if (size <=0 )return null ;
31+ TreeNode node =new TreeNode (preorder [s1 ]);
32+ if (size ==1 )return node ;
33+ int pos =s2 ;
34+ while (pos <= (s2 +size -1 )) {
35+ if (inorder [pos ] ==preorder [s1 ])break ;
36+ ++pos ;
37+ }
38+ int leftlen =pos -s2 ;
39+ node .left =buildTreeRe (preorder ,s1 +1 ,inorder ,s2 ,leftlen );
40+ node .right =buildTreeRe (preorder ,s1 +leftlen +1 ,inorder ,pos +1 ,size -leftlen -1 );
41+ return node ;
42+ }
43+ }
