🏷️199. Binary Tree Right Side View

---

1. 문제 설명

• 이진 트리의 루트가 주어지면, 그것의 오른쪽에 서 있는 것으로 상상해보세요. 위에서 아래로 정렬된 볼 수 있는 노드의 값들을 반환하세요.

---

2. 접근 방법

방법 1) [실패] DFS탐색

• 오른쪽에서 봤을때 보이는 숫자를 출력하는데 dfs 탐색으로 오른쪽 자식 노드만 탐색하면 금방 해결될 문제라고 생각하였습니다. - 그렇게 코드를 구현하였고 테스트케이스가 잘 동작하여 문제가 없구나 ~ 라고 빠르게 풀었네 라고 생각하면서 제출하였지만 전제의 오류가 있었습니다.
• 실패 이유 : 아래의 그림과 같이 root = [1, 2]일 경우 오른쪽에서 숫자를 봤을 때 오른쪽 자식 노드가 없어 왼쪽 자식 노드가 보이게 되는 경우도 생각을 해봐야 했습니다.
  

import java.util.*;

class Solution {

    List<Integer> list = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root);
        return list;
    }

    public void dfs(TreeNode node){

        if(node != null){
            list.add(node.val);
            dfs(node.right);
        }
    }
}

방법 2) [성공😊] BFS 탐색

• Queue & BFS 탐색을 통해 데이터를 순회하며 조회를 합니다.
• 이때 이진 트리의 Level n 순으로 순회를 하게 되는데, 해당 level의 마지막 노드가 오른쪽에서 보았으때 보이는 숫자이므로 list에 저장하여 결과값을 만들었습니다.

---

3. 구현 코드

import java.util.*;

class Solution {

    // 결과값 저장 변수 선언
    List<Integer> list = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        bfs(root);
        return list;
    }

    // BFS 탐색
    public void bfs(TreeNode root){

        // root가 null인 경우 예외처리
        if(root == null)
            return;

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

        while(!queue.isEmpty()){

            int len = queue.size();
            while(len-- > 0 ){
                TreeNode node = queue.poll();
                
                if (len == 0)   // 해당 레벨의 마지막 데이터인 경우 list에 저장
                    list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
            }  
        }
    }
}

---

4. 최종 회고

• 처음에는 DFS로 접근하여 풀려고 하였지만 전제의 오류로 인하여 실패하였습니다. DFS 방법으로 해당 오류를 처리하여 풀 수도 있었지만 BFS로 푸는 것이 논리적으로는 편한 방법이라고 생각하여 BFS로 풀었습니다.
• 주어진 문제에서 예외 케이스가 없는지 잘 확인하며 풀고, 엣지 케이스를 생각해보며 여러 테스트 케이스를 시도하여 정확도를 높이는 알고리즘을 만들어야 겠습니다.