題目

給定一個二叉樹的根節點 root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。

一、代碼實現

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func rightSideView(root *TreeNode) []int {if root == nil {return []int{}}var result []intqueue := []*TreeNode{root}for len(queue) > 0 {levelSize := len(queue)for i := 0; i < levelSize; i++ {node := queue[0]queue = queue[1:]if i == levelSize-1 {result = append(result, node.Val)}if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}}return result
}

二、算法分析

1. 核心思路

• 層次遍歷（BFS）：利用隊列進行廣度優先搜索，記錄每層最后一個節點值
• 右視圖特性：每層最右側節點即為該層可見的節點

2. 關鍵步驟

1. 隊列初始化：根節點入隊
2. 層級遍歷：記錄當前層節點數，遍歷時保留下一層節點
3. 右節點捕獲：當遍歷到當前層最后一個節點時記錄值
4. 子節點入隊：按順序處理左右子節點

3. 復雜度

指標	值	說明
時間復雜度	O(n)	每個節點遍歷一次
空間復雜度	O(n)	隊列最大存儲空間為最寬層節點數

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 空樹：返回空數組
• 完全左斜樹：返回根節點到最底層左節點的路徑
• 單節點樹：返回單個元素的數組

2. 多語言實現

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def rightSideView(self, root: TreeNode) -> List[int]:if not root:return []result = []queue = [root]while queue:level_size = len(queue)for i in range(level_size):node = queue.pop(0)if i == level_size - 1:result.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return result

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();if (i == levelSize - 1) {result.add(node.val);}if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}}return result;}
}

五、總結與擴展

1. 核心創新點

• 層級遍歷特性：利用BFS天然的分層特性獲取右視圖
• 高效判斷邏輯：通過層級索引直接定位最右節點

2. 擴展應用

• 左視圖：改為記錄每層第一個節點
• 對角線視圖：修改節點入隊順序和記錄策略
• Z型遍歷：結合層級奇偶性改變遍歷方向

3. 工程優化

• 雙向隊列：使用Deque提升出隊效率
• 層級緩存：預先緩存層級大小避免動態計算
• 內存優化：每層處理完后及時釋放引用