654-最大二叉树

LeetCode 654. Maximum Binary Tree

LeetCode-654

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums.

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

method: 递归

可以直接传下标，不用再构造数组

• 用个maxIndex就可以了，不需要maxValue
• begin==end说明前面最大值在边界，传的是[begin,end)，相等的话就是空

下标要从begin开始了。maxIndex已经是下标了，就不用再begin+maxIndex

TreeNode* traversal(vector<int>& nums, int begin, int end) {
    if (begin >= end) return nullptr;   // 最大值在最右边或最左边
    int maxIndex = begin;   // 从begin开始
    for (int i = begin; i < end; i++) { // 从begin开始
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }
    TreeNode* root = new TreeNode(nums[maxIndex]);
    root->left = traversal(nums, begin, maxIndex);  // 左闭右开
    root->right = traversal(nums, maxIndex + 1, end);
    return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    return traversal(nums, 0, nums.size());
}

类似题目：108-数组转为二叉搜索树