LeetCode 654. 最大二叉树

654. 最大二叉树

题目：给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

链接 https://leetcode.cn/problems/maximum-binary-tree/

其他思路

1. 递归
   （1）最简单的方法是直接按照题目描述进行模拟。
   （2）我们用递归函数construct(nums,left,right) 表示对数组 nums 中从nums[left] 到 nums[right] 的元素构建一棵树。我们首先找到这一区间中的最大值，记为 nums 中从 nums[best]，这样就确定了根节点的值。随后我们就可以进行递归：左子树为 construct(nums,left,best−1)；右子树为construct(nums,best+1,right)。
   （3）当递归到一个无效的区间（即 left>right）时，便可以返回一棵空的树。

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def construct(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            
            best = left
            for i in range(left + 1, right + 1):
                if nums[i] > nums[best]:
                    best = i
        
            node = TreeNode(nums[best])
            node.left = construct(left, best - 1)
            node.right = construct(best + 1, right)
            return node
        
        return construct(0, len(nums) - 1)

2. 单调栈
   
   

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        stk = list()
        left, right = [-1] * n, [-1] * n
        tree = [None] * n

        for i in range(n):
            tree[i] = TreeNode(nums[i])
            while stk and nums[i] > nums[stk[-1]]:
                right[stk[-1]] = i
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        
        root = None
        for i in range(n):
            if left[i] == right[i] == -1:
                root = tree[i]
            elif right[i] == -1 or (left[i] != -1 and nums[left[i]] < nums[right[i]]):
                tree[left[i]].right = tree[i]
            else:
                tree[right[i]].left = tree[i]
        
        return root

还可以把最后构造树的过程放进单调栈求解的步骤中，省去用来存储左右边界的数组

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        stk = list()
        tree = [None] * n

        for i in range(n):
            tree[i] = TreeNode(nums[i])
            while stk and nums[i] > nums[stk[-1]]:
                tree[i].left = tree[stk[-1]]
                stk.pop()
            if stk:
                tree[stk[-1]].right = tree[i]
            stk.append(i)
        
        return tree[stk[0]]

复杂度分析

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

参考：
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-binary-tree/solution/zui-da-er-cha-shu-by-leetcode-solution-lbeo/