题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
  public:
    int cnt = 0;
    TreeNode* build(vector<int>& pre, int l2, int r2, vector<int>& vin) {
        if (l2 > r2)return NULL;
        TreeNode* result = new TreeNode(pre[cnt]);
        int k = l2;
        for (; k <= r2; k++)
            if (pre[cnt] == vin[k])break;
        cnt++;
        result->left = build(pre, l2, k - 1, vin);
        result->right = build(pre, k + 1, r2, vin);
        return result;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        return build(pre, 0, vin.size() - 1, vin);
    }
};