Construct Binary Tree from Preorder and Inorder Traversal.txt

/**
 * Definition for binary tree
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int p = 0;
        return build(preorder, p, inorder, 0, inorder.size() - 1);
    }
    TreeNode* build(vector<int>& po, int& p, vector<int>& io, int l, int u) {
        if (l > u)
            return NULL;
        int v = po[p++], i = l;
        TreeNode* root = new TreeNode(v);
        while (io[i] != v)
            i++;
        root->left = build(po, p, io, l, i-1);
        root->right = build(po, p, io, i+1, u);
        return root;
    }
};