Construct Binary Tree from Preorder and Inorder Traversal

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

T:
We know the root node of current tree is the first element of the preorder traversal. We can iterate through the ignored traversal to find that root node. Then we know the length of the left subtree and right subtree.

A:

/**
 * 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 *build(vector< int > & preorder, int ps, int pe, vector< int > & inorder, int is, int ie) {
        if(ps > pe) {
            return NULL;
        }
        TreeNode * node = new TreeNode(preorder[ps]);
        int in = -1;
        for(int i=is; i<=ie; i++) {
            if(inorder[i] == preorder[ps]) {
                in = i;
                break;
            }
        }
        if(in == -1) {
            return node;
        }
        node->left = build(preorder, ps+1, ps+in-is, inorder, is, in-1);
        node->right = build(preorder, ps+in-is+1, pe, inorder, in+1, ie);
        return node;
    }
    TreeNode *buildTree(vector< int > &preorder, vector< int > &inorder) {
        return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};