Binary Tree Right Side View

문제

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.

오른쪽에서 트리를 보았을때의 모습을 출력하면 된다.

풀이

• 같은 레벨일 경우 right를 저장하고 같은 레벨에서 right가 없다면 left를 저장
• 오른쪽에서 보았을 때의 모습은 먼저 right 부분을 우선적으로 탐색하여 depths에 저장한다.
• depths에 저장되어 있지 않은 레벨의 노드는 추가해준다.

수도 코드

depth = dict() # key=level, value=node val
q = bfs 탐색을 위한 큐 생성
q에 level=0, root 데이터를 추가한다.

while q가 빌때까지:
	level, node = q.popleft()
    
    if depth에 level이 없다면:
    	depth에 (level, node.val) 추가
    
    if node의 right가 null이 아니라면:
    	q에 (level + 1, node.right) 추가
    if node의 left가 null이 아니라면:
    	q에 (level + 1, node.left) 추가

Solution(Runtime: 4ms)

import java.util.*;


class Solution {
    static class Pair {
        public int level;
        public TreeNode node;

        public Pair(int l, TreeNode n) {
            level = l;
            node = n;
        }
    }

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return List.of();
        }

        Map<Integer, Integer> depths = new HashMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, root));

        while (!q.isEmpty()) {
            Pair now = q.poll();
            TreeNode node = now.node;

            if (!depths.containsKey(now.level)) {
                depths.put(now.level, node.val);
            } 

            if (node.right != null) {
                q.add(new Pair(now.level + 1, node.right));
            }
            if (node.left != null) {
                q.add(new Pair(now.level + 1, node.left));
            }
        }

        return depths.entrySet()
                    .stream()
                    .map(entry -> entry.getValue())
                    .collect(Collectors.toList());
    }
}

return 부분은 아래코드를 stream을 사용하여 가독성을 높였다.

List<Integer> result = new ArrayList<>();
for (var entry: depths.entrySet()) {
    result.add(entry.getValue());
}
return result;