1. 105

construct-binary-tree-from-preorder-and-inorder-traversal

2. 算法

http://www.cnblogs.com/grandyang/p/4296500.html

• O(n)

3. 代码

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
private:
    TreeNode* dfs(vector<int>& preorder,vector<int>& inorder,int ps,int is,int len){
        if(len<=0)
            return NULL;
        TreeNode *root=new TreeNode(preorder[ps]);
        for(int i=0;i<len;i++)
            if(inorder[is+i]==root->val){
                root->left=dfs(preorder,inorder,ps+1,is,i);
                root->right=dfs(preorder,inorder,ps+i+1,is+i+1,len-i+1);
                break;
        }
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return dfs(preorder,inorder,0,0,preorder.size());
    }
};