[Leetcode] 102. Binary Tree Level Order Traversal - JS

https://leetcode.com/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 
같은 레벨별 왼쪽에서 오른쪽 순서대로 순회한 node.val을 배열로 반환하라.

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

 

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 levelOrder = function(root) {
    if (!root) return [];
    const res = [];
    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;
        const levelArr = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            levelArr.push(node.val)
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(levelArr);
    }
    return res;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

BFS 순회에 대한 개념이 점점 더 확실해지는 것 같다.

더 연습해보자.