JZ4重建二叉树

一、
思路：https://blog.nowcoder.net/n/c56eeb5b1845432a903db1c3c0cbc80a?f=comment
https://blog.nowcoder.net/n/7131c90ce3214472887b0f2f6652f5a7?f=comment

代码

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        return rebuild(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
    TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right, vector<int>& vin, int vin_left, int vin_right) {
        if (pre_left > pre_right || vin_left > vin_right) return nullptr;

        TreeNode* root = new TreeNode(pre[pre_left]);
        for (int i=vin_left; i<=vin_right; ++i) {
            if (vin[i] == root->val) {
                root->left = rebuild(pre, pre_left+1, pre_left+i-vin_left, vin, vin_left, i-1);
                root->right = rebuild(pre, pre_left+i-vin_left+1, pre_right, vin, i+1, vin_right);
                break;
            }
        }
        return root;
    }
};

或

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int pre_left=0;
        int pre_right=pre.size()-1;
        int vin_left=0;
        int vin_right=vin.size()-1;
        if(pre.size()==0 || vin.size()==0)
            return nullptr;
        TreeNode* root=new TreeNode(pre[pre_left]);
        int rootIndexInVin= vin_left;
        for(int i=0;i<=vin_right;++i){
            if(vin[i]==root->val){
                rootIndexInVin=i;
                break;
            }
        }
        vector<int> preLeft,preRight,vinLeft,vinRight;
        for(int i=0;i<rootIndexInVin;++i){
            vinLeft.push_back(vin[i]);
            preLeft.push_back(pre[i+1]);
        }
        for(int i=rootIndexInVin+1;i<=vin_right;++i){
            vinRight.push_back(vin[i]);
            preRight.push_back(pre[i]);
        }
        root->left=reConstructBinaryTree(preLeft,vinLeft);
        root->right=reConstructBinaryTree(preRight,vinRight);
        return root;

    }
};