[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

😎풀이

너비 우선 탐색의 개념을 활용하여 풀면 좋은 문제이다.

dfs로도 풀 수 있지만 개념은 bfs에 가깝기에 해당 방법으로 풀이해보았음

부모 요소를 우선적으로 살펴보며 isReverse flag를 toggle 하는 방식으로 역행 여부를 결정하였음

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if(!root) return [];
    const result = [];
    const queue = [root];
    let isReverse = false;
    // bfs
    while(queue.length) {
        // queue 변화 이전 순회 수 결정
        const thisLoopCount = queue.length;
        // 현재 deps의 노드 배열
        const currentArr = [];
        for(let i = 0; i < thisLoopCount; i++) {
            // 현재 deps를 처리 후 다음 deps로 leaf node 입력
            const curNode = queue.shift();
            currentArr.push(curNode.val);
            if(curNode.left) queue.push(curNode.left);
            if(curNode.right) queue.push(curNode.right);
        }
        // 역행 차례라면, 반대의 배열로 입력
        result.push(isReverse ? currentArr.reverse() : currentArr)
        isReverse = !isReverse
    }

    return result
};