题解 | #重建二叉树#

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = vin.size();
        if(n == 0)
            return NULL;
        //分别存放前序和中序遍历时某个根结点的左子树元素数组和右子树元素数组
        vector<int> pre_left, pre_right, vin_left, vin_right;
        TreeNode* root = new TreeNode(pre[0]);  //新建根结点
        int gen = 0;
        for(int i = 0; i < n; i++){
            if(vin[i] == pre[0]){  //在中序遍历的数组中找到前序遍历的根结点所在的位置
                gen = i;  //记录根结点下标位置，切分为左右子树数组
                break;
            }
        }
        for(int i = 0; i < gen; i++){   //
            vin_left.push_back(vin[i]);  //根结点左边的是左子树数组，仍旧是中序，
            pre_left.push_back(pre[i+1]); //+1是因为根结点已经占了一个位置，前序左子树数组
        }  
        for(int i = gen+1; i<n; i++){
            vin_right.push_back(vin[i]);  //中序右子树数组
            pre_right.push_back(pre[i]);  //前序右子树数组
        }
        //递归返回左子树和右子树的根结点，即当前根结点的左孩子和右孩子
        root->left = reConstructBinaryTree(pre_left, vin_left); //找到左子树的根结点
        root->right = reConstructBinaryTree(pre_right, vin_right); //找到右子树的根结点
        return root;
    }
};