您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 199 Binary Tree Right Side View：層序遍歷取最右節點

編輯：關於C++

問題描述

給定一棵二叉樹，站在樹的右側看，返回從上到下可見的節點值。例如：

    1            ←
   / \
  2   3         ←
   \   \
    5   4       ←
輸出：[1, 3, 4]

核心思路：BFS 層序遍歷

每一層最右側的節點即為右視圖可見節點。使用隊列按層遍歷，記錄每層最後一個節點。

Java 實現（標準 BFS）

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            TreeNode node = queue.poll();
            // 最後一個節點加入結果
            if (i == size - 1) res.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return res;
}

優化版：雙隊列/單隊列+分隔符


// 原代碼風格：用兩個 List 交替模擬隊列
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    
    List<TreeNode> curr = new ArrayList<>();
    List<TreeNode> next = new ArrayList<>();
    curr.add(root);
    res.add(root.val);
    
    while (!curr.isEmpty()) {
        for (TreeNode node : curr) {
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        if (!next.isEmpty()) 
            res.add(next.get(next.size() - 1).val);
        curr.clear();
        curr.addAll(next);
        next.clear();
    }
    return res;
}

DFS 遞歸替代方案

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, 0, res);
    return res;
}

void dfs(TreeNode node, int depth, List<Integer> res) {
    if (node == null) return;
    // 先遍歷右子樹，確保每層首次訪問的是最右節點
    if (depth == res.size()) res.add(node.val);
    dfs(node.right, depth + 1, res);
    dfs(node.left, depth + 1, res);
}

DFS 優先走右子樹，首次到達新深度時即為最右節點，代碼更簡潔。