[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal, Solution

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

[Thoughts]

There is an example.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

The preorder and inorder traversals for the binary tree above is:

preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}

The first node in preorder alwasy the root of the tree. We can break the tree like:
1st round:
preorder:  {7}, {10,4,3,1}, {2,8,11}
inorder:     {4,10,3,1}, {7}, {11, 8,2}

        _______7______
       /              \
    {4,10,3,1}       {11,8,2}

Since we alreay find that {7} will be the root, and in "inorder" sert, all the data in the left of {7} will construct the left sub-tree. And the right part will construct a right sub-tree. We can the left and right part agin based on the preorder.

2nd round
left part                                                                            right part
preorder: {10}, {4}, {3,1}                                              {2}, {8,11}
inorder:  {4}, {10}, {3,1}                                                {11,8}, {2}

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4      {3,1}   {11,8}

see that, {10} will be the root of left-sub-tree and {2} will be the root of right-sub-tree.

Same way to split {3,1} and {11,8}, yo will get the complete tree now.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

So, simulate this process from bottom to top with recursion as following code.

[Code]

1:    TreeNode *buildTree(  
2:      vector<int> &preorder,   
3:      vector<int> &inorder) {  
4:      // Start typing your C/C++ solution below  
5:      // DO NOT write int main() function  
6:      return BuildTreePI(  
7:        preorder, inorder, 0, preorder.size()-1, 0, preorder.size());  
8:    }    
9:    TreeNode* BuildTreePI(  
10:      vector<int> &preorder,  
11:      vector<int> &inorder,  
12:      int p_s, int p_e,  
13:      int i_s, int i_e)  
14:    {  
15:      if(p_s > p_e)  
16:        return NULL;  
17:      int pivot = preorder[i_s];  
18:      int i =p_s;  
19:      for(;i< p_e; i++)  
20:      {  
21:        if(inorder[i] == pivot)  
22:          break;  
23:      }  
24:      TreeNode* node = new TreeNode(pivot);  
25:      node->left = BuildTreePI(preorder, inorder, p_s, i-1, i_s+1, i-p_s+i_s);  
26:      node->right = BuildTreePI(preorder, inorder, i+1, p_e, i-p_s+i_s+1, i_e);  
27:      return node;      
28:    }