题解 | #重建二叉树#

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0 || vin.size()==0)    return nullptr;

        // 找到根节点的值，并构建根节点
        int rootval = pre[0];
        TreeNode* root = new TreeNode(rootval);

        // 找到根节点在中序数组中的位置，可以标志左右子树的节点各有多少个
        int index=0;
        for(; index<vin.size(); index++) {
            if(vin[index] == rootval) {
                break;
            }
        }
        // 切割数组 vin
        vector<int> vinleft(vin.begin(), vin.begin()+index);
        vector<int> vinright(vin.begin()+index+1, vin.end());
        // 切割数组 pre
        vector<int> preleft(pre.begin()+1, pre.begin()+1+index);
        vector<int> preright(pre.begin()+1+index, pre.end());

        // 递归生成左右子树
        root->left = reConstructBinaryTree(preleft, vinleft);
        root->right = reConstructBinaryTree(preright, vinright);

        // 返回根节点
        return root;
    }
};