赞
踩
给定一个不含重复元素的整数数组 nums
。一个以此数组直接递归构建的最大二叉树定义如下:
nums
中的最大元素;返回有给定数组 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
的节点。- 空数组,无子节点。
- 来源: 力扣(LeetCode)
- 链接: https://leetcode-cn.com/problems/maximum-binary-tree
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums
中的所有整数 互不相同实际上,从题目要求就可以看出,此题需要使用递归的方式直接构建最大二叉树最为方便。
from collections import deque from typing import List, Optional class TreeNode: def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None): self.val = val self.left = left self.right = right class Solution: def construct_maximum_binary_tree(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return maximum = max(nums) index = nums.index(maximum) root = TreeNode(maximum) root.left = self.construct_maximum_binary_tree(nums[:index]) root.right = self.construct_maximum_binary_tree(nums[index + 1:]) return root def main(): nums = [3, 2, 1, 6, 0, 5] sln = Solution() root = sln.construct_maximum_binary_tree(nums) tree = [] visiting = deque([root]) while visiting: node = visiting.popleft() if node: tree.append(node.val) visiting.append(node.left) visiting.append(node.right) else: tree.append(None) while True: if not tree[-1]: tree.pop() else: break print(tree) # [6, 3, 5, None, 2, 0, None, None, 1] if __name__ == '__main__': main()
实际上,上述代码的空间复杂度还可以进一步优化,因为在上述的解法中在递归调用时重复使用了 Python 的列表切片操作,该操作是会额外的分配列表空间,在最坏的情况下即当给定列表有序时,最坏的空间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
对此,下面给出优化后的代码:
from collections import deque from typing import List, Optional class TreeNode: def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None): self.val = val self.left = left self.right = right class Solution: def _maximum_num(self, nums: List[int], start: int, stop: int) -> int: maximum = nums[start] for i in range(start + 1, stop + 1): if maximum < nums[i]: maximum = nums[i] return maximum def _maximum_binary_tree(self, nums: List[int], start: int, stop: int) -> Optional[TreeNode]: if start > stop: return maximum = self._maximum_num(nums, start, stop) index = nums.index(maximum, start, stop + 1) root = TreeNode(maximum) root.left = self._maximum_binary_tree(nums, start, index - 1) root.right = self._maximum_binary_tree(nums, index + 1, stop) return root def maximum_binary_tree(self, nums: List[int]) -> Optional[TreeNode]: return self._maximum_binary_tree(nums, 0, len(nums) - 1) def main(): nums = [3, 2, 1, 6, 0, 5] sln = Solution() root = sln.maximum_binary_tree(nums) tree = [] visiting = deque([root]) while visiting: node = visiting.popleft() if node: tree.append(node.val) visiting.append(node.left) visiting.append(node.right) else: tree.append(None) while True: if not tree[-1]: tree.pop() else: break print(tree) # [6, 3, 5, None, 2, 0, None, None, 1] if __name__ == '__main__': main()
针对上述代码,需要特别注意的几点为:
_maximum_num()
方法,是因为 Python 内置的 max()
函数并不支持通过指定可迭代对象的元素起始和终止索引的方式来查找最大值,这也就导致了一开始的解答中需要利用切片从原列表中获得指定起始和终止索引的列表;_maximum_num()
方法中,待返回值 maximum
的起始值不能随便指定,而需要是 nums[start:stop]
中的一个元素,否则会产生预料之外的问题;maximum = nums[start]
之后,做了一个细微的优化,即 for
循环迭代时选择 nums
的起始索引从 start + 1
开始。maximum_binary_tree
一共被调用
n
n
n 次。每次递归寻找根节点时,需要遍历当前索引范围内所有元素找出最大值。最坏的情况下,数组 nums
有序,总的复杂度为
O
(
n
2
)
O(n^2)
O(n2) 。Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。