[Leetcode] 199. Binary Tree Right Side View - JS

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 오른쪽에서 보고있다고 가정하고 
최상층에서 최하층 순서대로 보이는 노드의 값들을 반환하라.

제한조건
--------------------
- 노드의 갯수는 0 ~ 100개이다.
- -100 <= node.val <= 100

 

2. 접근 방법

접근방법
--------------------
BFS로 순회하면서 노드를 담는다.
BFS로 순회 시 다음 레벨의 자식 노드를 순서대로 담으므로 
자식 노드의 갯수만큼 반복문을 실행해줘서 그 때마다 우측의 노드로 갱신해준 값을 
반복문 종료시 추가해준다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if (!root) return [];
    
    const rightNodes = [];
    const queue = [root];

    while (queue.length) {
        const childrenNodeLength = queue.length;
        let rightMostNode = null;

        for (let i = 0; i < childrenNodeLength; i++) {
            const node = queue.shift();

            rightMostNode = node;

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        if (rightMostNode) rightNodes.push(rightMostNode.val)
    }
    
    return rightNodes
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

BFS(깊이 우선 탐색)하여 왼쪽 자식부터 우선적으로 queue 자료구조에 추가하고 rightMostNode에 queue에서 선입선출한 node를 갱신해주면서 자식 노드의 갯수만큼 반복문을 실행해준다.

반복문이 종료되었을 때, 가장 우측에 존재한 node가 rightMostNode에 할당되므로 이 때, rightNodes 배열에 추가해준다.

 

문제를 딱 보자마자 BFS 로 풀어야 겠다고 바로 떠오르진 않았지만 몇분 고민해보니 BFS 방법으로 풀어야겠다고 생각이 들었다.

근데, BFS를 구현했던 적이 오래전이라 다시 기억이 가물가물해져 GPT를 통해 공부했다.

 

예전에 알고리즘 수업 때 공부했던 BFS 코드도 다시 보니 이해가 잘되었다.