Leetcode 654.最大二叉树

1.题目描述

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

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

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

输入：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 的节点。
    • 空数组，无子节点。

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

提示：

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

2.思路分析

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

2.1 递归法

递归函数要处理的参数以及返回值

参数:

• 数组nums、 begin/end(下标)

返回值:

• 指向节点的指针

def traversal(nums: List[int], begin: int, end: int) -> TreeNode:
1

终止条件

传入数组的大小<1时,说明遍历到了叶子节点

# 列表长度为0时返回空节点
if begin == end:
    return None
1
2
3

确定单层搜索逻辑

• 1. 找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。

  # 找到最大的值和其对应的下标
  max_index = begin
  for i in range(begin, end):
      if nums[i] > nums[max_index]:
          max_index = i
          
  # 构建当前节点
  root = TreeNode(nums[max_index]
  1
  2
  3
  4
  5
  6
  7
  8

• 2.最大值所在的下标左区间 构造左子树、最大值所在的下标右区间 构造右子树

  # 递归构建左右子树
  root.left = traversal(nums, begin, max_index)
  root.right = traversal(nums, max_index + 1, end)
  1
  2
  3

2.2 单调栈

根据题目对树构建的描述可知，nums 中任两节点所在构建树的水平截面上的位置仅由下标大小

决定。 不难想到可抽象为找最近元素问题，可使用单调栈求解。

• 初始时，只有一个根节点，其中存储了整个数组；

• 在每一步操作中，可以「任选」一个存储了超过一个数的节点，找出其中的最大值并存储在该节 点。 最大值左侧的数组部分下放到该节点的左子节点，右侧的数组部分下放到该节点的右子节点；

• 如果所有的节点都恰好存储了一个数，那么构造结束。

当我们选择的节点中数组的最大值为 nums[i] 时，所有大于 nums[i] 的元素已经被构造过（即被

单独放入某一个节点中），所有小于nums[i] 的元素还没有被构造过。

说明：

在最终构造出的树上，以 nums[i] 为根节点的子树，在原数组中对应的区间，左边界为 nums[i]

左侧第一个比它大的元素所在的位置，右边界为 nums[i] 右侧第一个比它大的元素所在的位

置。左右边界均为开边界。

如果某一侧边界不存在，则那一侧边界为数组的边界。如果两侧边界均不存在，说明其为最大

值，即根节点。

并且

nums[i] 的父结点是两个边界中较小的那个元素对应的节点。

问题转化为:

找出每一个元素左侧和右侧第一个比它大的元素所在的位置。

单调栈的处理逻辑如下:

• 如果当前元素 > 栈顶元素, 栈顶元素出栈
• 如果当前元素 ≤ 栈顶元素, 直接入栈

当然，在对比两个节点大小和出入栈的同时，依然还是会根据题意，进行二叉树的构造。即：

• 如果当前元素 > 栈顶元素(出栈), 当前元素.left = 栈顶元素
• 如果当前元素 ≤ 栈顶元素(入栈), 栈顶元素.right = 当前元素

举个栗子:nums = [3,2,1,6,0,5]为例，逐步分析如何通过单调栈构建二叉树

• 对于数组中的前三个元素，满足nums[2]> nums[1] > nums[0]，所以，这三个元素直接入栈
  

• 当遍历到num[3]=6, 此时6>1, nums[0]出栈,同理 nums[1], nums[2]也要出栈,此时栈为空,nums[3]入栈
  
  
  

• 当遍历到nums[4] =0,此时0<6,直接入栈
  

• 当遍历到nums[5]=5, 此时5>0,nums[4]出栈
  

• 最后栈内仅剩余nums[3]与nums[5]
  

3.代码实现

3.1 递归法(DFS)

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

        def traversal(nums: List[int], begin: int, end: int) -> TreeNode:
            # 列表长度为0时返回空节点
            if begin == end:
                return None

            # 找到最大的值和其对应的下标
            max_index = begin
            for i in range(begin, end):
                if nums[i] > nums[max_index]:
                    max_index = i

            # 构建当前节点
            root = TreeNode(nums[max_index])

            # 递归构建左右子树
            root.left = traversal(nums, begin, max_index)
            root.right = traversal(nums, max_index + 1, end)

            return root

        return traversal(nums, 0, len(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i(0≤i
• 空间复杂度：O(n)，即为最坏情况下需要使用的栈空间。

3.2 单调栈

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        # 单调栈(栈顶->栈底:递增)
        # 本题问题转换为求解每个元素左侧和右侧第一个比它的元素的位置
        n = len(nums)
        stack = []
        tree = [None] * n

        for i in range(n):
            # 当前节点建树
            tree[i] = TreeNode(nums[i])
            # 如果栈存在且当前元素 > 栈顶元素, 栈顶元素出栈,当前元素.left = 栈顶元素
            while stack and nums[i] > nums[stack[-1]]:
                tree[i].left = tree[stack[-1]]
                stack.pop()
            # 当栈不为空,此时当前元素 < 栈顶元素 栈顶元素.right = 当前元素
            if stack:
                tree[stack[-1]].right = tree[i]
            # 其余情况,元素直接入栈(当前元素 ≤ 栈顶元素)
            stack.append(i)
        # 遍历结束,返回栈底元素构建的树
        return tree[stack[0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。单调栈求解左右边界和构造树均需要 O(n)的时间。
• 空间复杂度：O(n)， 即为单调栈和数组 tree 需要使用的空间。