題目
#

leetcode 199 - Binary Tree Right Side View (題目說明請點連結)

題目簡述
#

給定一個二元樹，返回從右側視角看到的節點值。從右側視角看，對於每一層，我們只能看到該層最右邊的節點。

範例
#

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: 從右側視角看到的節點值分別為 1、3、4。

Example 2:

Input: root = [1,null,3]
Output: [1,3]
Explanation: 從右側視角看到的節點值分別為 1、3。

Example 3:

Input: root = []
Output: []
Explanation: 空樹沒有節點。

解題思路
#

這題要求我們從二元樹的右側視角看到的節點值。也就是說，對於每一層，我們需要返回該層最右邊的節點值。

解法
#

方法一：迭代（BFS）
#

使用BFS，逐層遍歷二元樹，對於每一層，我們記錄該層最右邊的節點值。

方法二：遞迴（DFS）
#

使用DFS，按照右子樹優先的順序遍歷，記錄每一層的第一個節點。

完整程式碼
#

BFS解法
#

java

import java.util.List;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new LinkedList<>(); // 用來存放每層最右邊的節點值
        if (root == null) {
            return result; // 如果樹為空，直接回傳空列表
        }
        
        Queue<TreeNode> queue = new LinkedList<>(); // 用於BFS的隊列
        queue.offer(root); // 先將根節點加入隊列
        
        while (!queue.isEmpty()) {
            int size = queue.size(); // 當前層的節點數量
            result.add(queue.peek().val); // 每層的第一個節點（即最右邊的節點）加入結果
            
            // 遍歷當前層的所有節點
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll(); // 取出隊首節點
                
                // 先加入右子樹，再加入左子樹，確保下一層最右邊的節點會先被處理
                if (node.right != null) {
                    queue.offer(node.right);
                }
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        
        return result; // 回傳所有層的最右邊節點值
    }
}

DFS解法
#

java

import java.util.List;
import java.util.LinkedList;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 建立一個LinkedList來存放每層最右邊的節點值
        List<Integer> result = new LinkedList<>();
        // 從根節點開始進行DFS，初始深度為0
        dfs(root, 0, result);
        // 回傳結果列表
        return result;
    }
    
   
    private void dfs(TreeNode node, int depth, List<Integer> result) {
        // 如果節點為空，直接返回
        if (node == null) {
            return;
        }
        
        // 當前深度等於結果列表的大小，代表這是該層第一個被訪問的節點（最右邊的節點）
        if (depth == result.size()) {
            result.add(node.val); // 將節點值加入結果
        }
        
        // 先遞迴右子樹，再遞迴左子樹，確保每層最右邊的節點最先被加入
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}