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,0,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, start, maxIndex - 1) root.right = helper(nums, maxIndex + 1, end) return root return helper(nums, 0, 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, x): # self.val = x # self.left = None # self.right = None class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode: if not nums: return stack, maxNum = [], max(nums) for num in (nums + [maxNum]):
cur = TreeNode(num) while stack and stack[-1].val <= num: # in stack, is TreeNode node = stack.pop() if stack and stack[-1].val <= num: stack[-1].right = node else: cur.left = node stack.append(cur) return stack[0].left
[LeetCode] 654. Maximum Binary Tree_Medium tag: stack
原文：https://www.cnblogs.com/Johnsonxiong/p/10867538.html