199. Binary Tree Right Side View (Java, recursion, Leetcode)

TreeNode의 node들이 주어졌을때 오른쪽에서 바라봤을때 보이는 값만 List로 출력하는 문제이다.

 

 

recursion과 depth를 이용하여 문제를 풀어야겠다는 아이디어는 구했으나 depth를 어떻게 적용할 수 있을지 감을 잡지 못해 다른 사람의 풀이를 참고하였다.

 

핵심 아이디어 코드는 다음과 같다.

if (depth == answer.size()) answer.add(node.val);
rightSide(node.right, depth + 1);
rightSide(node.left, depth + 1);

 

root 레벨에서부터 값을 차례대로 넣기 때문에 depth == answer.size()라는 조건이 성립한다.

같은 레벨일 때는 항상 최우측부터 체크하여 좌측으로 차례대로 방문을 하고

해당 레벨의 값을 넣은 적이 없으면 (현재 노드의 우측이 전부 null일 때) 해당 노드의 값을 answer에 넣어준다.

 

depth마다 최우측의 값을 찾을때마다 answer에 값을 넣어 size()가 영구적으로 증가하므로 이후 해당 depth에 해당하는 좌측의 값을 방문하게 되더라도 값이 변경되지 않는다.

 

전체코드

/**
 * 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 {
    List<Integer> answer = new ArrayList<>();
    
    private void rightSide(TreeNode node, int depth) {
        if (node == null) return;
        
        if (depth == answer.size()) answer.add(node.val); 
        rightSide(node.right, depth + 1);
        rightSide(node.left, depth + 1);
    }
    public List<Integer> rightSideView(TreeNode root) {
        rightSide(root, 0);
        
        return answer;
    }
}