199. Binary Tree Right Side View

Binary Tree Right Side View - LeetCode

주어진 이진 트리의 루트 노드를 오른쪽에서 볼 때, 상단부터 하단까지 볼 수 있는 노드의 값을 반환합니다.

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: []

 

문제 요약:

주어진 이진 트리에서 오른쪽에서 가장 오른쪽에 위치한 노드를 상단부터 하단까지 차례로 나열한 리스트를 반환하는 문제입니다.

 

풀이 과정: DFS

1. 깊이 우선 탐색(DFS)을 사용하여 트리를 순회합니다.
2. 재귀적으로 트리를 탐색하면서 현재 레벨(level)을 기록합니다.
3. 결과를 저장할 리스트를 생성하고, 현재 레벨에 처음 도달하는 경우 해당 노드의 값을 결과 리스트에 추가합니다.
4. 왼쪽 서브트리를 먼저 탐색하고, 오른쪽 서브트리를 나중에 탐색하여 오른쪽에서 가장 오른쪽에 있는 노드를 찾아냅니다.
5. 결과 리스트를 반환합니다.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> retList = new ArrayList<>();

        dfs(root, retList, 0);

        return retList;
    }

    private void dfs(TreeNode node, List<Integer> retList, int level){
        if(node == null) return;

        if(level == retList.size()){
            retList.add(node.val);
        }

        dfs(node.right, retList, level +1);
        dfs(node.left, retList, level +1);
    }
}

 

 

풀이 과정: BFS

1. 오른쪽 노드의 값을 저장할 빈 목록 result을 초기화합니다.
2. 이진 트리의 root가 null인지 확인합니다. 만약 root가 null이면 트리에 노드가 없으므로 빈 result 목록을 반환합니다.
3. 레벨 순서로 트리를 탐색하기 위한 큐(선입선출 자료 구조)를 생성합니다.
4. 큐에 root 노드를 추가하여 탐색을 시작합니다.
5. 큐가 비어있을 때까지 계속되는 루프를 시작합니다. 이 루프는 이진 트리의 레벨을 순차적으로 탐색합니다.
6. 루프 내부에서 현재 레벨의 노드 수를 큐의 크기를 확인하여 얻습니다(levelSize).
7. 현재 레벨에서 가장 오른쪽에 있는 노드를 추적하기 위한 변수 rightmost를 초기화합니다. 초기값은 null입니다.
8. 현재 레벨의 노드를 반복합니다. 각 노드에 대해서:
   a. 큐의 맨 앞에서 노드를 꺼내서 제거합니다.
   b. 현재 노드가 현재 레벨에서 가장 오른쪽 노드이므로 rightmost 변수를 현재 노드로 업데이트합니다.
   c. 현재 노드의 왼쪽 자식과 오른쪽 자식(존재하는 경우)을 큐에 추가합니다. 이 작업은 다음 레벨의 탐색을 준비합니다.
9. 현재 레벨의 모든 노드를 처리한 후, rightmost 노드의 값을 result 목록에 추가합니다. 이 값은 현재 레벨의 가장 오른쪽 값입니다.
10. 다음 레벨(있는 경우)을 처리하기 위해 루프를 반복합니다.
11. 루프가 완료되면 result 목록에는 이진 트리의 각 레벨에서 가장 오른쪽 노드의 값이 포함됩니다.
12. 최종적으로 result 목록을 반환합니다. 이 목록은 이진 트리의 오른쪽 뷰를 나타냅니다.
    요약하면, 이 BFS 알고리즘은 트리를 레벨 순서로 탐색하고 각 레벨에서 가장 오른쪽 노드를 추적하여 결과 목록에 추가합니다. 결과 목록은 트리의 각 레벨에서 가장 오른쪽 노드의 값을 포함하게 됩니다.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> retList = new ArrayList<>();
        if(root == null) return retList;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int levelDept = queue.size();
            TreeNode rightNode = null;
            for(int i = 0; i < levelDept ; i++){
                TreeNode node = queue.poll();
                rightNode = node;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            retList.add(rightNode.val);
        }
        return retList;
    }
}