199. Binary Tree Right Side View

문제 링크: https://leetcode.com/problems/binary-tree-right-side-view/

문제

이진 트리를 오른쪽에서 바라봤을 때 보이는 노드를 위에서 아래의 순서대로 배열을 반환하자.

위와 같은 트리는 [1, 3, 4] 를 반환

입력

• 이진트리의 root

출력

• 정수 배열

---

나의 풀이

접근

처음에는 당연히 오른쪽에서 보면 오른쪽 노드만 보이기 때문에, 오른쪽 노드만 탐색하면 해결될 줄 알았다.

하지만 잘 생각해보면, 모든 노드가 결과의 후보가 될 수 있다.

• root의 왼쪽 하위 트리 노드 (오른쪽 하위트리의 높이 < 왼쪽 하위트리의 높이 일 경우)
• root의 오른쪽 하위 트리, 오른쪽 노드
• root의 오른쪽 하위 트리, 왼쪽 노드

⇒ root와 같은 높이에 있는 노드 중, 가장 오른쪽에 있는 노드가 결과에 포함된다

왼쪽 하위 트리의 왼쪽 노드 < 왼쪽 하위 트리의 오른쪽 노드 < 오른쪽 하위 트리의 왼쪽 노드 < 오른쪽 하위 트리의 오른쪽 노드

root부터 아래로 내려오며, 존재하는 노드 중 가장 오른쪽 노드를 리스트에 추가하자

구현 코드

class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        list1.add(root.val);
        list2.add(root.val);

        order(root.right, list1);
        order(root.left, list2);

        int list1Size = list1.size();
        int list2Size = list2.size();

        if (list1Size < list2Size) {
            list1.addAll(list2.subList(list1Size, list2Size));
        }

        return list1;
    }

    public void order(TreeNode node, List<Integer> list) {
        if (node == null)
            return;
        
        list.add(node.val);
        order(node.right, list);
        order(node.left, list);
    } 
}

이 풀이는 테스트 케이스를 반만 통과했다.

원인은 바로, order 함수에서 해당 노드의 오른쪽 하위트리 순회 후, 왼쪽 하위트리를 순회하는데 이때 만약 해당 노드가 왼쪽과 오른쪽 하위트리 둘 다 가지게 되면, 결국 모든 노드를 가지게 됐었다. 착각을 단단히 하고 코드를 짰었다.

---

다른 풀이

전엔 stack 을 이용했었지만, 아래 코드는 BFS와 queue 를 이용하는 코드이다.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null)
            return new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        List<Integer> res = new ArrayList();
        
        while(!queue.isEmpty()){
            int size = queue.size();
            
            while (size -- > 0){
                TreeNode cur = queue.poll();
                if (size == 0)
                    res.add(cur.val);
                
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        
        return res;
    }
}

• root노드를 확인해 null이면 빈 배열 return

• queue를 생성해 root 노드를 삽입

• queue가 빌 때까지 다음 작업 반복

  • 현재 큐에 있는, 같은 층에 있는 노드들의 left와 right 노드 수만큼 반복문 진행
  • size가 0 일때 cur 노드는 같은 층에 있는 노드 중 가장 오른쪽(마지막) 노드이다. 따라서 res 리스트에 추가
  • 현재 노드의 왼쪽 노드와 오른쪽 노드가 있다면 큐에 추가

Queue의 특성인 FIFO, 선입선출을 이용해 왼쪽 노드가 먼저 들어가게끔 해서 제일 나중에 Queue에서 나오는 노드가 가장 오른쪽 노드임을 잘 이용한 코드다.