[Binary Tree - BFS, Medium] Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=leetcode-75

BFS, 큐 사용해서 순회하되 각 레벨의 마지막 원소만 result List에 add하면 될 것 같다.

즉 while문이 한 번 돌 때마다 que에서 가장 마지막에 있는 것만 넣으면 된다.

처음에는 아예 자식 중 맨 오른쪽 원소만 que에 넣는 방식으로 했었는데
그럼 left로 이어지는 케이스는 다루지 못한다. 생각을 깊게 하자

요약

• left나 right가 null이 아니면 큐에는 계속 추가해야 함
• 다만 while 한 번 순회시(level) 마다 큐에서 가장 끝에있는 원소를 result에 넣어야 함 (레벨 별로 순회해야 하므로 한 번 순회마다 큐에 있는 자식들을 전부 넣는다)

i == queSize - 1이면 큐의 마지막 원소

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

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int queSize = que.size();
            for (int i=0; i<queSize; i++) {
                TreeNode current = que.poll();
                
                if (i == queSize - 1) {
                    result.add(current.val);
                }

                if (current.left != null) {
                    que.offer(current.left);
                }
                if (current.right != null) {
                    que.offer(current.right);
                }
            }
        }
        return result;
    }
}