106. Construct Binary Tree from Inorder and Postorder Traversal

A typical recursive solution. Must be familiar with the property of inorder and postorder traversal.
(1) With postorder traversal, the root must be the last element in the array.
(2) With inorder traversal, the subarray on root's left forms the left child subtree and the subarray on root's right forms the right child subtree.
With the two properties above, we can solve the problem recursive.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {  
13:      if (inorder.empty()) return NULL;  
14:      return helper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &inorder, int is, int ie, vector<int> &postorder, int ps, int pe) {  
17:      if (ie < is || pe < ps) return NULL;  
18:      int i = is;  
19:      for (;i < ie; i++) {  
20:        if (inorder[i] == postorder[pe]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(postorder[pe]);  
23:      node->left = helper(inorder, is, i-1, postorder, ps, ps+i-is-1);  
24:      node->right = helper(inorder, i+1, ie, postorder, ps+i-is, pe-1);  
25:      return node;  
26:    }  
27:  };  

Note we have a loop to find the root position in inorder array. We can actually improve the algorithm by hashmap the value and its position first.