[Leetcode Top Interview 150] 199. Binary Tree Right Side View

난이도 : medium

문제링크

• root로부터 오른쪽 측면에서 보았을때 보이는 노드들을 출력하라

 

1. 접근법

• 해당 노드 전부를 전위표현식으로 방문하여 리스트에 집어넣음
• 그리고 오른쪽부터 방문하면서 해당 레벨에서 존재하는 가장 오른쪽 노드를 리스트의 인덱스로 찾아냄
• 방문하면서 answer 배열에 가장 오른쪽 노드 값을 집어넣음

 

2. 의사코드

dfs(root);

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

while (queue.isEmpty()) {
	// depth 별 answer를 구한다
}

public void dfs(TreeNode root) {
	if (root == null) {
    	return;
    }
    
	list.add(root);
	dfs(root.right);
    dfs(root.right);
}

 

3. 구현 코드

• 구현실패
• queue에서 뽑은 값이 어떤 뎁스인지 알 수 없음
• 또한 list에 담긴 int값들이 어느 뎁스의 값인지 알기 어려움

 

6. 회고

class Solution {        
    public List<Integer> rightSideView(TreeNode root) {                        
        List<Integer> answer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return answer;
        }
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode currentNode = queue.poll();
                if (i == 0) answer.add(currentNode.val);
                if (currentNode.right != null) queue.offer(currentNode.right);
                if (currentNode.left != null) queue.offer(currentNode.left);
            }
        }

        return answer;
    }    
}

• 출처 : NickWhite_youtube
• 방문한 노드의 레벨에서 오른쪽 노드부터 큐에 집어넣음
• 첫번째 노드를 answer 배열에 추가
  • 큐에서 뽑은 처음 노드는 해당 레벨에서 가장 오른쪽에 있는 노드
• 나머지 노드들은 queue에 노드를 추가하기 위해 사용함
  • 해당 레벨에서 가장 오른쪽에 있는 노드를 모두 후보군에 넣어야 하기 때문