654. 最大二叉树

Difficulty

Medium

Tags

二叉树

URL

https://leetcode-cn.com/problems/maximum-binary-tree/

Star

❤

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

二叉树的根是数组 nums 中的最大元素。

左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。

右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

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

示例 1：


输入：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：


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

提示：

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

nums 中的所有整数 互不相同

通过次数45,307提交次数55,970

法1 递归法

思路

在每一层递归程序，只负责找到当前的最大值，然后用这个最大值构造一个节点，节点的左右子树分别再用递归去构造。

题解


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

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self.build(nums=nums, left=0, right=len(nums))
    def build(self, nums, left, right):
			  #  此处动笔画一下！ 就知道如果left == right 已经是空了
        if left >= right:
            return None
        # 查找nums[left:right)之中最大的值  区间是左闭右开的
        indexMax = left
        valMax = nums[left]
        for i in range(left, right):
            if nums[i] > valMax:
                indexMax = i
                valMax = nums[i]
        node = TreeNode(valMax)
        node.left = self.build(nums, left, indexMax)
        node.right = self.build(nums, indexMax+1, right)
        return node

上述代码是采用控制nums的左右下标来控制nums数组的，还可以采用改变nums的方式，这样就是不用调用子函数了


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])
        
        # 找到最大值 最大值的下标
        curVal = nums[0]
        curIdx = 0
        for i in range(1,len(nums)):
            if nums[i] > curVal:
                curVal = nums[i]
                curIdx = i
            
        curNode = TreeNode(curVal)
        curNode.left = self.constructMaximumBinaryTree(nums[0:curIdx])
        curNode.right = self.constructMaximumBinaryTree(nums[curIdx+1:])

        return curNode

法2 迭代数组法

思路

遍历nums数组，逐个将数组中的元素添加到树上面。

具体添加策略：

对数组中元素nums[i]新建节点 cur = Treenode(nums[i])

如果根节点root为空 or 当前根节点小于新的节点 root.val < cur.val，那么需要更新根节点:

原先root节点挂到cur左子树

将cur 更新为新的root节点

如果不满足条件2，即root节点存在且当前根节点值大于新节点值，则需要将新节点挂在根节点右边：

从根节点开始向右查找，直到找到比cur.val小的：

将比cur.val小的节点挂到cur左边，再将cur节点替换到该节点的位置上

题解


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        root = None
        for num in nums:
            # 1.新建节点
            cur = TreeNode(num)
            if root is None or root.val < cur.val:
                cur.left = root
                root = cur
            # 2.向右查找第一个小于cur.val的值
            else:
                tempnode = root # 新建的临时节点，用来辅助查找第一个小于cur的节点
                while tempnode.right and tempnode.right.val > num:
                    tempnode = tempnode.right
                cur.left = tempnode.right
                tempnode.right = cur

        return root