[leetCode]Construct Binary Tree from Preorder and Inorder Traversal

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 struct TreeNode {
 5     int val;
 6     TreeNode  *left;
 7     TreeNode  *right;
 8     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9 };
10 class Solution {
11 public:
12     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
13         TreeNode * head = build(preorder,0,preorder.size()-1,inorder,0, inorder.size()-1);
14         return head;
15     }
16 
17     TreeNode *build(vector<int> &preorder, int preStart,int preEnd,vector<int> &inorder, int inStart, int inEnd){
18         if(preStart == preEnd) return new TreeNode(preorder[preStart]);
19         if(preStart > preEnd)    return NULL;
20         int head = preorder[preStart];
21         int i = 0;
22         int size = preEnd - preStart+1;
23         for(; i<size;i++){
24             if(inorder[i+inStart] == head){
25                 break;
26             }
27         }
28         TreeNode *node = new TreeNode(head);
29         node->left = build(preorder,preStart+1,preStart+i,inorder, inStart, inStart+i-1);
30         node->right = build(preorder, preStart+1+i,preEnd,inorder,inStart+1+i,inEnd);
31         return node;
32 
33     }
34 };