题目名称

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。

递归地在最大值 左边 的 子数组前缀上 构建左子树。

递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例

输入：nums = [3,2,1,6,0,5]

输出：[6,3,5,null,2,0,null,null,1]

题解

这道题主要考察递归的思想

  1. 首先遍历数组，找出数组中最大的元素及元素序号， 并将该元素设置当前树节点值
  2. 根据序号，将数组分成两部分
  3. 当前树节点左节点 为最大元素左侧数组组成的树（循环第一步和第二步）
  4. 当前树节点右节点 为最大元素右侧数组组成的树（循环第一步和第二步）

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var constructMaximumBinaryTree = function(nums) {
    return converArray2Tree(nums, 0, nums.length - 1)
};

function converArray2Tree(nums, start, end) {
    if(end < start) return null
    let max = nums[start], maxIndex = start, root = {}
    for(let i = start; i <= end; i++) {
        if(nums[i] > max) {
            max = nums[i]
            maxIndex = i
        }
    }
    root.val = max
    root.left = converArray2Tree(nums, start, maxIndex - 1)
    root.right = converArray2Tree(nums, maxIndex + 1, end)
    return root
}