lc.654 最大二叉树

![[Pasted image 20241128010158.png	500]]
![[Pasted image 20241128010241.png	300]]

![[Pasted image 20241128010704.png]]

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size() - 1);
    }

    TreeNode* construct(const vector<int>& nums, int left, int right) {
	    
	    //若为无效区间
        if (left > right) {
            return nullptr;
        }

		//找到最大元素的下标best
        int best = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[best]) {
                best = i;
            }
        }

		//把最大元素结点"挂(return)"上去
        TreeNode* node = new TreeNode(nums[best]);

		//递归
        node->left = construct(nums, left, best - 1);
        node->right = construct(nums, best + 1, right);
        
        return node;
    }
};