1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(preorder.size() <= 0 || inorder.size() <= 0)
            return NULL;
        TreeNode * root = buildTreeStep(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
        return root;
    }
private:
    TreeNode *buildTreeStep(vector<int> &preorder,int prea,int preb, vector<int> &inorder,int ina,int inb) {
        if(prea > preb || ina > inb)
            return NULL;
        int root = preorder[prea];
        int i;
        for(i = ina;i <= inb;i++) {
            if(inorder[i] == root) {
                break;
            }
        }
        //inorderleft:ina,i-1
        //inorderright,i+1,inb
        //preorderleft:prea+1,prea+1+(i-1)-ina
        //preorderright:prea+(i-1)-ina+1,preb
        TreeNode * node = new TreeNode(root);
        node->left = buildTreeStep(preorder,prea+1,prea+1+(i-1)-ina,inorder,ina,i-1);
        node->right = buildTreeStep(preorder,prea+1+(i-1)-ina+1,preb,inorder,i+1,inb);
        return node;
    }
};