[Leetcode] 199. Binary Tree Right Side View

문제정의

binary tree의 root가 주어졌을 때, 오른쪽 측면에 서있다고 상상하고 위에서부터 아래로 차례대로 볼 수 있는 노드의 값을 반환하라.

https://leetcode.com/problems/binary-tree-right-side-view/

Binary Tree Right Side View - LeetCode

 

풀이

처음엔 너무 단순하게 생각해서 root를 시작점으로 오른쪽 노드만 탐색하는 재귀함수를 짰다가 바로 틀려버렸다.

틀린 테스트 케이스가 [1, 2, 3, 4]였는데 [1, 3, 4]를 출력하지 않고, [1, 3] 만 출력하고 있었다.(값인 2인 노드는 1의 왼쪽 노드이기 때문에 탐색하지 않았음)

너무 잠오는 와중에 풀어서 쉽게 생각했구나.. 하고 씻으러 갔다가 문제의 핵심은 오른쪽 측면에서 볼 수 있는 값이기 때문에 각 depth별로 가장 오른쪽의 노드 값을 찾아야함을 깨달았다. 그리고 가장 오른쪽 노드의 값이라고 해서 항상 그 노드가 부모의 오른쪽 노드가 아니라는 것!

Queue를 활용해서 각 depth별로 TreeNode를 넣고, depth의 가장 마지막 value를 정답 배열에 추가해준다.

    class Solution {
        
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            if (root == null) {
                return result;
            }

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

            while(!queue.isEmpty()) {
                int size = queue.size();

                TreeNode curr = new TreeNode();
                for (int i=0; i<size; i++) {
                    curr = queue.poll();
                    
                    if (curr.right != null) {
                        queue.add(curr.right);
                    } else if (curr.left != null){
                        queue.add(curr.left);
                    }
                }
                result.add(curr.val);

            }
            return result;
        }
    }