BFS應用題 Find Largest Value in Each Tree Row Leetcode #515

Raychan null on Unsplash

這題的題目在這裡:

題目敘述

題目會給我們一顆二元樹的根結點，要求我們找出每一層最大的節點值。

測試範例

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:

[1] Python O(n) by level-order traversal. 78%+ [w/ Hint] - Find Largest Value in Each Tree Row - LeetCode