[LeetCode] 199. Binary Tree Right Side View - Java[자바]

링크

문제

이진 트리의 root가 주어졌을 때, 자신이 그 오른쪽에 서 있다고 상상하고 위에서 아래로 순서대로 보이는 노드의 값을 반환합니다.

풀이

결과를 담을 리스트를 하나 준비한 후, 루트에서 부터 각 레벨의 가장 오른쪽 노드의 값을 리스트에 담는다.

레벨에 따른 노드를 처리할 것이므로, BFS를 고려해볼 수 있다.

class Solution {  
  
    public List<Integer> rightSideView(TreeNode root) {  
	    // 결과를 저장할 리스트
        List<Integer> result = new ArrayList<>();  
        if (root == null) {  
            return result;  
        }  
        // BFS를 위한 Queue  
        Queue<TreeNode> q = new LinkedList<>();  
        // root를 Queue에 넣는다.
        q.add(root);  
			  
        // BFS
        while (!q.isEmpty()) {  
        	// 같은 레벨에 속한 Node의 개수
            int size = q.size();  
            TreeNode node = null;  
            for (int i = 0; i < size; i++) {  
                // Queue에서 Node 한개를 가져온다.
                node = q.poll();  
                
                // 해당 노드의 자식이 있으면 Queue에 추가한다.
                if (node.left != null) {  
                    q.add(node.left);  
                }  
                if (node.right != null) {  
                    q.add(node.right);  
                }  
            }  
            // node는 같은 레벨에서의 가장 오른쪽 Node일 것이므로
            // Node의 값을 결과 리스트에 넣는다.
            result.add(node.val);  
        }  
  
        return result;  
    }  
}

입력이 [1,2,3,null,5,null,4] 인 경우,

Queue에는 1이 들어간 후, 1개의 크기만큼 for 문을 돌면서 1의 left인 2와 right인 3이 들어가게 되고, 결과 리스트에 1을 넣는다.

다음 단계에서는 size가 2가 될 것이고, 5와 4를 Queue에 넣게 된다.. 이런 식으로 반복하게 된다.

주석으로 코드에 대한 설명을 적어두었다.