[LeetCode] 654. Maximum Binary Tree_Medium tag: stack
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
? Construct the maximum tree by the given array and output the root node of this tree. Example 1: Input: [3,2,1,6,5] Output: return the tree root node representing the following tree: 6 / 3 5 / 2 0 1 ? Note:
1. divide and conquer,最坏的时间复杂度为O(n^2),average 时间复杂度为 O(n * lg n). Code # 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 def helper(nums,start,end): if start > end: return if start == end: for index,num in enumerate(nums[start : end + 1],start): #start from start if index == start or num > nums[maxIndex]: maxIndex = index root = TreeNode(nums[maxIndex]) root.left = helper(nums,maxIndex - 1) root.right = helper(nums,maxIndex + 1,end) return root return helper(nums,len(nums) - 1) ? 2. 实际上这个题目类似于[LeetCode] 84. Largest Rectangle in Histogram_Hard tag: stack, 我们实际上求的是每个num的向左第一个比num大的数,和向右第一个比num大的数,取其中较小的,作为parent node,所以我们要用到strict decreasing stack,这里我们将maxNum加到nums的后面,这样能保证最后的结果。 Code:? ?T: O(n) # Definition for a binary tree node. # class TreeNode: # def __init__(self,nums: List[int]) -> TreeNode: if not nums: return stack,maxNum = [],max(nums) for num in (nums + [maxNum]): (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |