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

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

Show Tags

//preorder储存数字信息
//inorder存储结构信息
//每次inorder都会把数平分成两半
//注意不要内存超界。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return _buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());    
    }
    TreeNode * _buildTree(vector<int>::iterator preorderBegin, vector<int>::iterator preorderEnd, vector<int>::iterator inorderBegin, vector<int>::iterator inorderEnd){
        if(preorderBegin == preorderEnd){
            return NULL;
        }
        int val = *preorderBegin;
        TreeNode* p = new TreeNode(val);
        size_t i;
        for(i = 0; inorderBegin + i != inorderEnd; i++){
            if(*(inorderBegin + i) == val){
                break;
            }
        }
        p->left = _buildTree(preorderBegin + 1, preorderBegin + i + 1, inorderBegin, inorderBegin + i);
        p->right = _buildTree(preorderBegin + 1 + i, preorderEnd, inorderBegin + i + 1, inorderEnd);
        return p;
    }
};