LeetCode | 0654. Maximum Binary

Problem

LeetCode

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bTSB8rfA-1609944183381)(https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg)]

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

Example 2:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w7UzhSQ2-1609944183394)(https://assets.leetcode.com/uploads/2020/12/24/tree2.jpg)]

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• All integers in nums are unique.

问题

力扣

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

1. 二叉树的根是数组 nums 中的最大元素。
2. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
3. 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树 。

示例 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3pLMglok-1609944183402)(https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg)]

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
  - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
    - 空数组，无子节点。
    - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
      - 空数组，无子节点。
      - 只有一个元素，所以子节点是一个值为 1 的节点。
  - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
    - 只有一个元素，所以子节点是一个值为 0 的节点。
    - 空数组，无子节点。

示例 2：

img

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

思路

递归

1. 遍历找到数组最大值和对应索引
2. 分别对最大值左右两边数组进行递归调用，构造左右子树

Python3 代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # 特判
        if not nums:
            return None
        
        # 找到数组中的最大值和对应的索引
        maxVal = max(nums)
        maxIndex = nums.index(maxVal)
 
        root = TreeNode(nums[maxIndex])
        # 递归构造左右子树
        root.left = self.constructMaximumBinaryTree(nums[:maxIndex])
        root.right = self.constructMaximumBinaryTree(nums[maxIndex + 1:])
        
        return root

GitHub 链接

• Python