题解 | #重建二叉树#老实人又来了~

这道题目前前后后做了好几遍，但是每一次都害怕写错了细节，所以多复习几遍准没错~

1. 首先我们要烂熟于心：前序：根左右；中序：左根右；后续：左右根

2. 那么，前序 + 中序就可以唯一确定一棵树，首先由前序确定根结点的值，然后中序找出根结点的位置，确定左右子树的结点个数；接着就可以采用递归思路求解了；
   中序 + 后续也是一样，首先由后序确定根结点的值，然后中序找出根结点的位置，确定左右子树的结点个数；接着就可以采用递归思路求解了；

贴一个之前写的总结

前序 + 中序

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> dp;//用于更快的查找根结点
    TreeNode* recur(vector<int> pre, vector<int> vin, int lPre,\
                    int rPre, int lVin, int rVin) {
        //边界
        if (lPre > rPre) return nullptr;

        //
        TreeNode* node = new TreeNode(pre[lPre]);
        int lenLeft = dp[pre[lPre]] - lVin;
        int lenRight = rVin -dp[pre[lPre]];
        node->left = recur(pre, vin, lPre + 1, lPre + lenLeft, lVin, lVin + lenLeft - 1);
        node->right = recur(pre, vin, lPre + lenLeft + 1, rPre, lVin + lenLeft + 1, rVin);
        return node;
    }
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //前序确定根结点的值，中序确定左右子树的部分，然后递归
        int len = pre.size();
        for (int i = 0; i < vin.size(); ++i) 
            dp[vin[i]] = i;
        return recur(pre, vin, 0, len - 1, 0, len - 1);
    }
};

中序 + 后续

/**
 * 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 {
private:
    unordered_map<int,int> mp;
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder,int in_left,int in_right,int post_left,int post_right){
        //由后序遍历可以得到根节点，然后可以从中序遍历得到左右子树的组成；
        if(in_left>in_right) return nullptr;

        //算出左子树长度
        int len_left=mp[postorder[post_right]]-in_left;

        TreeNode* root=new TreeNode(postorder[post_right]);
        root->left=dfs(inorder,postorder,in_left,in_left+len_left-1,post_left,post_left+len_left-1);
        root->right=dfs(inorder,postorder,in_left+len_left+1,in_right,post_left+len_left,post_right-1);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len=inorder.size();
        for(int i=0;i<len;++i)
            mp[inorder[i]]=i;
        return dfs(inorder,postorder,0,len-1,0,len-1);
    }
};