题解 | #重建二叉树#

/**
 * 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.size() == 0) return nullptr;
        int root = pre[0];
        TreeNode *node = new TreeNode(root);
        if(pre.size() == 1) return node;
        auto pos = find(vin.begin(),vin.end(),root);
        int left = pos - vin.begin();
        int right = vin.end() - pos - 1;
        node->left = reConstructBinaryTree(vector<int>(pre.begin()+1,pre.begin()+1+left), vector<int>(vin.begin(),vin.begin()+left));
        node->right = reConstructBinaryTree(vector<int>(pre.begin()+1+left,pre.end()), vector<int>(vin.begin()+left+1,vin.end()));
        return node;
    }
};