Solution

• 根据索引来划分区间

/**
 * 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) {
        return construct(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
private:
    TreeNode* construct(const vector<int> pre, int preBegin, int preEnd,
                        const vector<int> vin, int vinBegin, int vinEnd) {
        if (preBegin > preEnd) return nullptr;
        TreeNode* root = new TreeNode(pre[preBegin]);
        // 在中序数组中寻找切割点
        int i;
        for (i = vinBegin; i <= vinEnd; ++i) {
            if (vin[i] == pre[preBegin]) break;
        }
        
        // 切割中序数组
        int vinLeftBegin = vinBegin;
        int vinLeftEnd = i - 1;
        int vinRightBegin = i + 1;
        int vinRightEnd = vinEnd;
        // 切割前序数组
        int preLeftBegin = preBegin + 1;
        int preLeftEnd = preLeftBegin + (vinLeftEnd - vinLeftBegin);
        int preRightBegin = preLeftEnd + 1;
        int preRightEnd = preEnd;
        
        root->left = construct(pre, preLeftBegin, preLeftEnd, vin, vinLeftBegin, vinLeftEnd);
        root->right = construct(pre, preRightBegin, preRightEnd, vin, vinRightBegin, vinRightEnd);
        return root;
    }
};