199. Binary Tree Right Side View - Medium

前往題目

之前有寫過

想法

• 一開始想法非常單純，只看右邊nodes
• 很快的寫出來發現如果左右不對稱(不等高)的話就行不通

思路

1. BFS
2. 每層的最右邊就是答案

Code

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> q = new LinkedList<>();

        q.add(root);

        // BFS
        while(!q.isEmpty()) {
            TreeNode rightNode = null;
            int size = q.size();

            for (int i = 0; i < size; ++i) {
                TreeNode curNode = q.poll();
                // 更新右邊node
                rightNode = curNode;
                if (curNode.left != null) q.offer(curNode.left);
                if (curNode.right != null) q.offer(curNode.right);
            }
            // 跳出迴圈時rightNode就是最右邊的那個，直接加入
            // 不用判斷是否為null因為迴圈裡寫了條件，不會加入null
            res.add(rightNode.val);
        }

        return res;
    }
}