題目敘述
題目會給我們一顆二元樹的根結點，要求我們找出每一層最大的節點值。
測試範例
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Example 2:
Input: root = [1,2,3]
Output: [1,3]
約束條件
Constraints:
- The number of nodes in the tree will be in the range
[0, 104]. -231<= Node.val <= 231- 1
演算法
題目要求找出每一層的節點最大值，聯想到逐層探索的level order traversal，也可以說以root根結點為起始點拜訪的BFS廣度優先探索。
從根結點開始，當作第一層，紀錄當下這一層的最大值，接著逐層往下拜訪。
沿途蒐集到的最大節點值，就是最終答案，也是題目所求。
程式碼
from collections import deque
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
if not root:
return []
traversal_queue = deque([root])
max_list = []
# Launch level-order traversal
while traversal_queue:
next_queue = deque([])
max_val = float('-inf')
for cur in traversal_queue:
# update max node value of current level
max_val = max( max_val, cur.val )
if cur.left:
next_queue.append( cur.left )
if cur.right:
next_queue.append( cur.right )
max_list.append( max_val )
# update traversal queue for next level
traversal_queue = next_queue
return max_list
複雜度分析
時間複雜度: O( n)
拜訪整棵樹耗費O(n)，每個節點拜訪一次。
空間複雜度: O(n)
BFS拜訪所用到的Queue，佔用空間最多也為O(n)
關鍵知識點
拜訪二元樹，在配合題目的要求一起看: 找出每一層的最大節點值，就想到經典的BFS模板，在二元樹中就是level order traversal。
強烈建議，同步複習高度關聯的應用題，鞏固二元樹+BFS拜訪的知識點。
Level order traversal I, Level order traversal II
Reference:
