NC12 #重建二叉树#

递归。注意下标！
先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素。
先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素。

class Solution {
public:
    unordered_map<int, int> index;
    TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right,vector<int>& in, int in_left, int in_right)
    {
        if (pre_left > pre_right)
            return nullptr;
        int root_val = pre[pre_left];
        int in_root = index[root_val];
        TreeNode* root = new TreeNode(root_val);
        int size_left_subtree = in_root - in_left;
        root->left = rebuild(pre, pre_left + 1, pre_left + size_left_subtree, in, in_left, in_root - 1);
        root->right = rebuild(pre, pre_left + size_left_subtree + 1, pre_right, in, in_root + 1, in_right);
        return root;
    }

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        for (int i = 0; i < n; i++)
            index[vin[i]] = i;
        return rebuild(pre, 0, n - 1, vin, 0, n - 1);
    }
};