[Leetcode]-- Construct Binary Tree from Inorder and Postorder Traversal

 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     public TreeNode buildTree(int[] inorder, int[] postorder) {
12         if (postorder == null || inorder == null) {
13             return null;
14         }
15         int postLen = postorder.length;
16         int inLen = inorder.length;
17         if (postLen == 0 || inLen == 0) {
18             return null;
19         }
20 
21         return constructTree(postorder, 0, postLen - 1, inorder, 0, inLen - 1);
22     }
23     
24     public static TreeNode constructTree(int[] postorder, int postStart, int postEnd,
25             int[] inorder, int inStart, int inEnd) {
26         int rootVal = postorder[postEnd];
27         TreeNode root = new TreeNode(rootVal);
28         root.left = null;
29         root.right = null;
30         
31         if(postStart == postEnd && postorder[postStart] == inorder[inStart]){
32             return root;
33         }
34         
35         int i = inStart;
36         for(; i <= inEnd; i++){
37             if(inorder[i] == rootVal){
38                 break;
39             }
40         }
41         int leftLen = i - inStart;
42         if(leftLen > 0){
43             root.left = constructTree(postorder, postStart, postStart + leftLen - 1,
44                     inorder, inStart, i - 1);
45         }
46         if(inEnd > i){
47             root.right = constructTree(postorder, postStart + leftLen, postEnd - 1,
48                     inorder, i + 1, inEnd);
49         }
50         return root;
51     }
52 }