105. Construct Binary Tree from Preorder and Inorder Traversal

Same idea as "106. Construct Binary Tree from Inorder and Postorder Traversal".

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>& preorder, vector<int>& inorder) {  
13:      if (preorder.empty() || preorder.size() != inorder.size()) return NULL;  
14:      return helper (preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &preorder, int ps, int pe, vector<int> &inorder, int is, int ie) {  
17:      if (ps > pe || is > ie) return NULL;  
18:      int i = is;  
19:      for (; i <= ie; i++) {  
20:        if (preorder[ps] == inorder[i]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(preorder[ps]);  
23:      node->left = helper(preorder, ps+1, ps+i-is, inorder, is, is+i-1);  
24:      node->right = helper(preorder, ps+i-is+1, pe, inorder, i+1, ie);  
25:      return node;  
26:    }  
27:  };