題目描述:給定一棵二元樹的根節點,假設你站在樹的右側向左看,回傳你能看到的節點值(由上到下排列)。即每一層最右邊的節點值。
解題思路:最直觀的解法是 BFS 層序遍歷——逐層處理節點,每層最後一個節點就是從右側可見的節點。使用佇列(queue)逐層展開:將根節點加入佇列,每輪迴圈記錄當前層的節點數 level_size,處理完整層後,該層最後一個節點的值加入結果。另一個等效解法是 DFS:先遞迴右子樹、再遞迴左子樹,並追蹤當前深度——每個深度第一次遇到的節點(即最右節點)加入結果。兩種方法時間複雜度相同,BFS 較直觀,DFS 程式碼更精簡。
時間複雜度:O(n) — 每個節點恰好入隊、出隊各一次。
空間複雜度:O(w) — 佇列最多同時存放一層的所有節點,w 為樹的最大寬度;最壞情況(完全二元樹最後一層)為 O(n/2) = O(n)。
1. If root is null, return []
2. Initialize queue Q with root
3. While Q is not empty:
a. levelSize = Q.size()
b. For i from 0 to levelSize-1:
i. node = Q.dequeue()
ii. If i == levelSize-1: append node.val to result
iii. If node.left exists: Q.enqueue(node.left)
iv. If node.right exists: Q.enqueue(node.right)
4. Return resultDFS(右優先)O(n):前序 DFS 時先走右子樹再走左子樹,追蹤當前深度 depth。若 depth == result.size(),代表這是該層第一次被訪問的節點(即最右節點),加入結果。程式碼更精簡,但若樹非常深可能有堆疊溢出風險。
左側視圖變形:只需將 BFS 中取「最後一個」改為取「第一個」,或 DFS 改為左子樹優先,即可得到左側視圖——展示此演算法的靈活性。