@@ -0,0 +1,1789 @@
+// Given preorder and inorder traversal of a tree, construct the binary tree.%0A%0A// Note:%0A// You may assume that duplicates do not exist in the tree.%0A%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    public TreeNode buildTree(int%5B%5D preorder, int%5B%5D inorder) %7B%0A    %09// some key ideas are that: %0A    %09// 1.first element of preorder is the root node.%0A    %09// 2.if found the root node's index in the in-order array, %0A    %09//   then indexes smaller than it represents left sub-tree, indexes larger than the %0A    %09//   root index represent the right sub-tree.%0A    %09// 3. each iteration we need to locate the root's index in in-order array.%0A    %09int pLen = preorder.length;%0A    %09int iLen = inorder.length;%0A    %09if(pLen != iLen %7C%7C pLen == 0) return null;%0A%0A    %09return helper(preorder, inorder, 0, pLen - 1, 0);%0A    %7D%0A%0A    public TreeNode helper(int%5B%5D preorder, int%5B%5D inorder, int iStart, int iEnd, int pIndex)%7B%0A    %09if(iStart %3E iEnd) return null;%0A    %09if(iStart == iEnd) return new TreeNode(inorder%5BiStart%5D);%0A%0A    %09int mid = 0;%0A%0A    %09for(int i = iStart; i %3C= iEnd; i++)%7B%0A    %09%09if(preorder%5BpIndex%5D == inorder%5Bi%5D)%7B%0A    %09%09%09mid = i;%0A    %09%09%09break;%0A    %09%09%7D%0A    %09%7D%0A%0A    %09TreeNode node = new TreeNode(inorder%5Bmid%5D);%0A    %09// why pIndex + 1: since in the preorder traversal, next element is the root of current%0A    %09// element's left subtree.%0A    %09node.left = helper(preorder, inorder, iStart, mid - 1, pIndex + 1);%0A    %09// why mid - istart + 1: it represents all the elements covered so far, which are all%0A    %09// less then the root node's value.%0A    %09node.right = helper(preorder, inorder, mid + 1, iEnd, pIndex + (mid - iStart + 1));%0A%0A    %09return node;%0A    %7D%0A%7D%0A

add construct binary tree from preorder and inorder traversal solution