654. 最大二叉树

原题链接：654. 最大二叉树

solution:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

class Solution {
public:
    unordered_map pos;
    TreeNode* constructMaximumBinaryTree(vector& nums) {
        int n = nums.size();
        for(int i = 0;i < n;i++) {
            pos[nums[i]] = i;   //构建数组的的值的索引
        }
        return Build(nums, 0, n);
    }

    TreeNode *Build(vector &nums,int l,int r) {
        if(l >= r) return nullptr;
        int maxval = INT_MIN;
        for(int i = l;i < r;i++) {
            maxval = max(maxval,nums[i]);
        }
        int dist = pos[maxval];
        TreeNode *root = new TreeNode(maxval);
        root->left = Build(nums, l, dist);
        root->right = Build(nums, dist + 1, r);
        return root;
    }
};