题解 | #重建二叉树#

前序的第一个结点就是根结点，并且将后序一分为二，再根据分割后序得到的左后序和右后序两部分，将前序也分为左前序和右前序两部分，这两部分对应地与后序的两部分大小相同。接着递归地重建左子树和右子树。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty()) return nullptr;
        int node_val=pre[0];
        TreeNode* root=new TreeNode{node_val};
        int in_index=0;
        for(int i=0;i<vin.size();i++){
            if(vin[i]==node_val){
                in_index=i;
                break;
            }
        }
        vector<int> pre_left{};
        vector<int> pre_right{};
        vector<int> in_left{};
        vector<int> in_right{};
        for(int i=1;i<pre.size();i++){
            if(i<=in_index) pre_left.push_back(pre[i]);
            else pre_right.push_back(pre[i]);
        }
        for(int i=0;i<vin.size();i++){
            if(i<in_index) in_left.push_back(vin[i]);
            else if(i>in_index) in_right.push_back(vin[i]);
        }
        root->left=reConstructBinaryTree(pre_left, in_left);
        root->right=reConstructBinaryTree(pre_right, in_right);
        return root;
    }
};