654. 最大二叉树
#树 2024-11-13 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    TreeNode* construct(vector<int>& nums, int left, int right){
        if(left > right) return nullptr;
        int index = getMaxIndex(nums,left,right);
        TreeNode* node = new TreeNode(nums[index]);
        node->left = construct(nums,left,index - 1);
        node->right = construct(nums,index + 1,right);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.empty()) return nullptr;
        return construct(nums,0,nums.size() - 1);
    }

private:
    int getMaxIndex(vector<int>& nums, int left, int right) {
        int maxIndex = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
};

真要被自己愚蠢死，这道题本身看题意就不难，就是从一定区间类找到最大值，基于此创建出一个节点，然后将其左右子节点指向当前函数，进行递归调用。

但我居然把 getMaxIndex 用二分法去实现，真是聪明反被聪明误，二分法只能处理有序，但是我为了找到下标，是不能把里面的元素进行有序的。

这道题还要注意的地方就是注意好传参的边界值是合理的，不然就会出错。这里的getMaxIndex的左右区间是[]，而不是[)。