0654. Maximum Binary Tree

题目信息

题号:

0654

难度:

Medium

主题:

不同整数数组、区间最大值、递归树结构

原题:

LeetCode 0654

重点:

整体最大值作为根、最大值左侧和右侧子数组分别递归构造左右子树、输入元素互不相同

题目重述

给定由互不相同整数构成的非空数组 nums,按以下唯一规则构造二叉树并返回根节点:当前数组中的最大元素成为根;最大元素左侧的连续子数组递归构造左子树,右侧连续子数组递归构造右子树。

空子数组对应空子树。nums.length 位于 [1, 1000],元素值位于 [0, 1000],所有值互不相同,因此每个递归区间中的最大值位置都是唯一的。

自建示例

最大值位于数组开头:

输入:nums = [5,1,4,2]
输出:[5,null,4,1,2]
解释:5 是整体最大值并成为根;右侧 [1,4,2] 的最大值 4 成为右孩子,其左右孩子分别由 [1] 和 [2] 构造。

数组严格递增:

输入:nums = [1,2,3]
输出:[3,2,null,1]
解释:每个区间的最大值都位于末尾,因此构造出的树只有连续的左孩子。