use the preorder && inorder to construct the tree

1. 规律

对于先序遍历分为三个部分

1
node [left tree] [right tree]

对于中序遍历分为三个部分

1
[left tree] node [right tree]

2. build the tree

主要是基于中序遍历进行操作，利用先序遍历去得到在中序遍历中的位置，每次遍历一个节点后进行+1，再递归地对子树进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* buildRoot(vector<int>&pre, vector<int>&in, int &root, int l, int r) {
        if (l > r) return NULL;
        int p = l;
        while (in[p] != pre[root]) p++;
        root++;
        TreeNode *newNode = new TreeNode(in[p]);
        newNode->left = buildRoot(pre, in, root, l, p-1);
        newNode->right = buildRoot(pre, in ,root, p+1, r);
        return newNode;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int root = 0;
        return buildRoot(preorder, inorder, root, 0, preorder.size()-1);
    }
};