[bfs] 199번 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.

이진 트리의 루트가 주어지면, 그 오른쪽에 서 있는 자신을 상상하고 위에서 아래로 정렬된 노드의 값을 반환합니다.

예시

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

제약

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

코드

const rightSideView = (root) => {
    if (!root) return [];
    
    const res = [];
    const queue = [[0, root]];
    
    while (queue.length > 0) {
        const [lev, currNode] = queue.shift();

        res[lev] = currNode.val;

        currNode.left && queue.push([lev + 1, currNode.left]);
        currNode.right && queue.push([lev + 1, currNode.right]);
    }
    
    return res;
};

풀이

• bfs로 전체 순회를 하며 각 노드에 lev를 조사하여 반환 받는다.
• 반환된 트리의 노드 형태는 [lev, node] 이다.
• 왼쪽 자식노드, 오른쪽 자식 노드 순으로 재귀를 진행한다.
• 반환된 트리를 순회하며 lev 별로 해당 lev의 마지막 노드를 결과에 집어 넣는다.