654 最大二叉树（递归、ST表）

川长思鸟来 2022-08-29 09:51 158阅读 0赞

**1. 问题描述：**

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

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

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

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

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

![20210801165116697.jpg][]

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

**提示：**

1 <= nums.length <= 1000  
0 <= nums\[i\] <= 1000  
nums 中的所有整数互不相同  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-binary-tree

**2. 思路分析：**

分析题目可以知道我们需要根据当前区间的最大值**递归**创建这颗二叉树，首先根节点是当前区间\[l, r\]的最大值，然后递归当前最大值的位置k的左右两边创建左右子树，最终返回根节点即可。所以这道题目的核心在于如何快速求解一个区间的最大值，最简单的方法是每一次扫描当前区间的所有数字然后求解最大值，但是时间复杂度为O(n ^ 2)所以是非常高的，每一次都是扫描当前的整个区间所以很容易超时。求解区间最值比较优秀的一般有以下几种方法：

*  线段树，线段树的好处是能够支持区间的修改
 *  ST表，ST表主要用来解决RMQ问题（RMQ问题属于区间静态问题==>区间的元素不需要修改），也即区间最大/小值的查询问题

由于这道题目的核心在于如何快速求解一个区间的最大值，所以我们需要使用一个比较好的算法来解决这个问题，上面列出的两种方法都是比较好的，由于ST算法的代码比较短，也比较好理解，所以下面采用ST算法快速求解区间的最值问题。

ST表是一种简单的数据结构，主要用来解决**RMQ问题**，ST算法主要使用了倍增的思想，本质上是一个简单的递推，递推的时候需要预处理一个二维数组dp，所以一开始的时候需要声明一个二维的dp数组，其中第一维的长度为n（n为nums数组的长度），第二维的长度为k + 1（k = logn），dp\[i\]\[j\]表示区间\[i，i + 2 ^ j - 1\]的最值，递推的时候以2 ^ (j - 1)作为分隔点分为左右两部分求解最值，所以dp的状态转移方程为dp\[i\]\[j\] = max\{dp\[i\]\[j - 1\]，dp\[i + 2 ^ (j - 1)\]\[j - 1\]\}，我们可以使用两层循环进行状态计算，第一层循环表示区间的某个起点i开始的长度为j，第二层循环表示区间的起点i，为什么第一层循环先是某个起点开始的长度呢？这是由dp数组的状态转移方程决定的，我们在状态转移的时候当前状态的值依赖于上一个状态的值，所以需要先计算出j - 1的状态那么才可以计算出当前状态j，所以最外层的循环为某个区间起点对应的长度j，预处理的时间复杂度为O(nlogn)，查询区间最值的时间复杂度为O(1)，所以整个算法的时间复杂度为O（nlogn）。在查询区间\[l， r\]最值的时候那么我们直接使用公式查询即可： a = dp\[l\]\[k\]，b = dp\[r - (1 << k) + 1\]\[k\]，其实也是以k = logn作为分隔点求解以分隔点k的左右两部分的最值即可，为什么使用分为两个部分来求解最值呢？因为只有两个部分同时求解最值才可以覆盖当前的区间的所有数字。因为我们需要递归创建左右子树，所以我们需要知道最大值对应的位置，所以在预处理的dp数组的时候dp数组存储的值为最大值对应的下标，这也是与一般求解最值问题的一个不同点，一般求见区间最值的时候存储的当前区间的最值，这里二维数组中存储的是下标，存储下标的时候获取的信息是更多的。通过下标那么可以知道两个信息，第一个是当前区间最值的位置，第二个是当前区间的最值。

![20210801175308467.png][]

**3. 代码如下：**

from typing import List
    import math
    
    
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        def query(self, l: int, r: int, nums: List[int], dp: List[List[int]]):
            range_l = r - l + 1
            # 以当前logn作为分隔点求解两个部分的最值
            k = int(math.log(range_l, 2))
            a = dp[l][k]
            b = dp[r - (1 << k) + 1][k]
            if nums[a] > nums[b]:
                return a
            return b
    
        def build(self, nums: List[int], dp: List[List[int]], l: int, r: int):
            if l > r: return None
            # 查询当前区间[l,r]的最大值, k为最值的区间
            k = self.query(l, r, nums, dp)
            root = TreeNode(nums[k])
            # 递归创建左右子树
            root.left = self.build(nums, dp, l, k - 1)
            root.right = self.build(nums, dp, k + 1, r)
            return root
    
        def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
            n = len(nums)
            k = int(math.log(n, 2))
            # dp列表预处理区间的最值对应的位置, 下面求解dp列表的过程就是预处理递推的过程
            dp = [[0] * (k + 1) for i in range(n)]
            for j in range(k + 1):
                i = 0
                while i + (1 << j) - 1 < n:
                    # 注意这里存储的是下标
                    if j == 0:
                        dp[i][j] = i
                    else:
                        # 利用2 ^ (j - 1)作为左右两部分的分隔点
                        l = dp[i][j - 1]
                        r = dp[i + (1 << j - 1)][j - 1]
                        if nums[l] < nums[r]:
                            dp[i][j] = r
                        else:
                            dp[i][j] = l
                    i += 1
            return self.build(nums, dp, 0, len(nums) - 1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/414e3de90b5c4680aeb666b95cd65b69.png
[20210801165116697.jpg]: /images/20220829/614692755aed4b9dae017c3f405c2d65.png
[20210801175308467.png]: /images/20220829/6ebbce631e4641209aa11f80e01c30a2.png