654.最大二叉树

链接：654.最大二叉树
难度：Medium
标签：栈、树、数组、分治、二叉树、单调栈
简介：返回 nums 构建的 最大二叉树 。

题解 1 - cpp

• 编辑时间：2022-08-20
• 执行用时：64ms
• 内存消耗：41.2MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return _constructMaximumBinaryTree(nums, 0, nums.size());
    }
    TreeNode* _constructMaximumBinaryTree(vector<int>& nums, int l, int r) {
        if (l >= r) return nullptr;
        int max_num = INT_MIN, max_idx;
        for (int i = l; i < r; i++) {
            if (nums[i] > max_num) {
                max_num = nums[i];
                max_idx = i;
            }
        }
        return new TreeNode(max_num, _constructMaximumBinaryTree(nums, l, max_idx), _constructMaximumBinaryTree(nums, max_idx + 1, r));
    }
};