[Leetcode] 103. Binary Tree Zigzag Level Order Traversal - JS

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

 

 

1. 문제 분석

문제분석
--------------------
이진트리의 Root가 주어졌을 때, 지그재그로 레벨별 순회하여 그 값들을 반환하라.
예를들어, 왼쪽 -> 오른쪽 방향으로 향했으면 다음 레벨에선 오른쪽에서 왼쪽 방향으로 교대로 향한다.

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

 

2. 접근 방법

접근방법
--------------------
BFS순회는 무조건 왼쪽에서 오른쪽 노드로 순회했다.
오른쪽에서 왼쪽으로 순회하려면 어떻게 해야할까?

방향을 나타내는 변수를 선언하여
왼쪽 먼저 Queue에 넣을지, 오른쪽 먼저 넣을지 구분해준다.
레벨별 순회가 종료되면 dir 방향을 바꿔준다.

방향을 정해줬으니 values에 넣을 때에도 그 방향대로 넣어주기 위해서 
레벨별 순회하기 전마다 queue 배열을 뒤집는다.

 

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

    const res = [];
    let queue = [root];
    let dir = true; // True가 왼쪽 -> 오른쪽, False가 오른쪽 -> 왼쪽

    while (queue.length) {
        let levelSize = queue.length;
        queue = queue.reverse();
        let values = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            values.push(node.val)

            if (dir) {
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            } else {
                if (node.right) queue.push(node.right);
                if (node.left) queue.push(node.left);
            }
        }
        dir = !dir
        res.push(values);
    }
    return res;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

BFS 순회에 대한 개념을 약간 꼬은 문제였다.

단순히 queue 배열에 왼쪽 오른쪽 넣어주는 순서만 바뀌면 될 줄 알았는데, valuse 배열에 값을 추가할 때에도

지그재그 순서가 반영되야하므로 queue 배열을 역순으로 바꿔주는 로직을 추가해줘야했다.

풀긴 풀었는데, 방향이 계속 바뀌니깐 좀 헷갈리는 문제였다.