[toc]

# leetcode 105 前序与中序构造二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
map<int,int> mp;
TreeNode* buildTree(vector& preorder, vector& inorder) {
for(int i=0;i<preorder.size();++i){
mp[preorder[i]]=i;
}

    return buildSubTree(preorder,inorder,0,inorder.size()-1);
}

TreeNode\* buildSubTree(vector<int>& preorder,vector<int>& inorder,int l,int r){
    if(l>r) return nullptr;
    int rId = findRoot(inorder,l,r);
    TreeNode\* root = new TreeNode(inorder\[rId\]);

    root->left = buildSubTree(preorder,inorder,l,rId-1);
    root->right = buildSubTree(preorder,inorder,rId+1,r);
    return root;
}

int findRoot(vector<int>& inorder,int l,int r){
    if(l==r) return l;
    int root = mp\[inorder\[l\]\];
    int inRoot = l;
    for(int i =l+1;i<=r;++i){
        int tempRoot = mp\[inorder\[i\]\];
        if(tempRoot<root){
            root = tempRoot;
            inRoot = i;
        }
    }
    return inRoot;
}

};

# leetcode 106 中序与后序构造二叉树

只需要把 105 的代码改一个大于小于号就可以了

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
map<int,int> mp;
TreeNode* buildTree(vector& inorder, vector& postorder) {
for(int i=0;i<postorder.size();++i){
mp[postorder[i]]=i;
}
return buildSubTree(postorder,inorder,0,inorder.size()-1);
}

TreeNode\* buildSubTree(vector<int>& postorder,vector<int>& inorder,int l,int r){
    if(l>r) return nullptr;
    int rId = findRoot(inorder,l,r);
    TreeNode\* root = new TreeNode(inorder\[rId\]);
    root->left = buildSubTree(postorder,inorder,l,rId-1);
    root->right = buildSubTree(postorder,inorder,rId+1,r);
    return root;
}
int findRoot(vector<int>& inorder,int l,int r){
    if(l==r) return l;
    int root = mp\[inorder\[l\]\];
    int inRoot = l;
    for(int i =l+1;i<=r;++i){
        int tempRoot = mp\[inorder\[i\]\];
        if(tempRoot>root){
            root = tempRoot;
            inRoot = i;
        }
    }
    return inRoot;
}

};