199. Binary Tree Right Side View, 자바 풀이

[문제]
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:

Input: root = []
Output: []

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static List<Integer> list;
    static int lev, visited[];
    public List<Integer> rightSideView(TreeNode root) {
        list = new ArrayList<>();
        visited = new int[100];
        lev = 0;

        bfs(root);

        System.out.println(list);

        return list;
    }

    static void bfs(TreeNode node) {
        if (node == null) {
            return;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                TreeNode nowNode = q.poll();
                if (nowNode == null) {continue;}

                // 가장 오른쪽에 위치하는 자식노드인 경우
                if (i == size - 1) {
                    list.add(nowNode.val);
                }

                if (nowNode.left != null) {
                    q.add(nowNode.left);
                }

                if (nowNode.right != null) {
                    q.add(nowNode.right);
                }
            }
        }
    }
}

// 주어진 BST(이진 탐색 트리)의 루트 노드를 기준으로 오른쪽 자식들의 값들을 구하여라!
// bfs 탐색을 사용하자. 현재 노드의 왼쪽과 오른쪽 자식들이 null 이 아니라면 q에 추가한다.
// 같은 level에서 가장 오른쪽 노드를 추가해야하기 때문에,
// 현재의 Queue 사이즈를 순회하며 레벨의 size - 1 순서의 노드만 추가한다.

처음에는 오른쪽 노드만 순회하며 답을 찾으면 되는줄 알았는데, 트리 전체를 순회하며 현재 level에서 가장 우측에 존재하는 노드를 찾아야 했다.

따라서 bfs 탐색을 통해 모든 노드를 탐색하되, 가장 우측의 노드만 추가하기 위해 Queue의 size - 1 노드만 찾는 로직이 필요했다.