學習路線/樹 — 廣度優先搜尋 (BFS)

199. 二元樹的右側視圖

Medium

Binary Tree Right Side View

TreeBreadth-First SearchBinary Tree

題目描述

給定一棵二元樹的根節點，想像自己站在它的右側，按由上到下的順序，回傳從右側所能看到的節點值。每一層只能看到最右邊的節點。

LeetCode 199原題連結 →

解法思路

  1. 使用 BFS（廣度優先搜尋）逐層遍歷二元樹
  2. 每層開始時記錄 s = len(q) 作為本層節點數
  3. 迴圈中若 i == s-1（本層最後一個節點），將其值加入結果
  4. 依序將左右子節點加入佇列，進入下一層

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(w)，w 為樹的最大寬度
當前層
0
1佇列2534

佇列 q

取出 ← 左 · · 右 → 加入

1
初始化：res=[]，佇列 q 放入根節點。BFS 開始，逐層取出節點。
1 / 10