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());

    }

};