[Refresh ! 코딩 테스트 / js] -103. Binary Tree Zigzag Level Order Traversal

문제해석

• bfs 구조를 유지하면서 output 값은 zigzag 으로 반환해주세요

첫번째 나의풀이

var zigzagLevelOrder = function(root) {
 //왼쪽 0 오른쪽 1 으로 지그제그 

    let queue=[[root,0,0]]
    let return_Arr=[];
    while(queue.length>0){
   
        let [first_push,point,index]= queue.shift();
        if(!first_push) continue;  
           console.log(point,first_push.val)
         if( !return_Arr[index]) return_Arr[index]=[first_push.val];
        
        else{
            if(point==1){
                return_Arr[index].unshift(first_push.val);
            }
            else{
                return_Arr[index].push(first_push.val);
            }
           
        }
     

        if(point==1){
            queue.push([first_push.right,!point,index+1])
            queue.push([first_push.left,!point,index+1])
        }
        else{
             queue.push([first_push.left,!point,index+1])
             queue.push([first_push.right,!point,index+1])
        }

    
    }
   return   return_Arr
};

• 지그재그를 위해서 point 값 ( 계속 변함) 에 따라서 queue에 결과물을 input 하면 되겠다.
• output 도 point 값에따라 변환해서 return_arr 에 넣으면 되지않을까?
• 실패 ㅠ

📉 문제점: 지그재그 방향에 따라 자식 노드를 다른 순서로 큐에 넣으면 레벨 순서가 꼬임
큐에 넣는 순서는 항상 왼→오로 넣고, 출력 시 순서만 바꾸는 방식이 정석입니다.
지금처럼 오른쪽부터 먼저 넣으면 다음 레벨의 순서가 잘못됩니다.

• 너무 복잡하게 생각했나보다..

변경 된 코드

var zigzagLevelOrder = function(root) {
    if (!root) return [];

    let queue = [root];
    let result = [];
    let leftToRight = true;

    while (queue.length > 0) {
        let levelSize = queue.length;
        let level = [];

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

            if (leftToRight) {
                level.push(node.val);
            } else {
                level.unshift(node.val);
            }

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

        result.push(level);
        leftToRight = !leftToRight;  // 다음 레벨은 방향 바꾸기
    }

    return result;
};

하지만 결과가 썩좋게 나오지 않았다

남의 코드

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if (root == null) return [];
    let queue = [root];
    let levels = [];
    let zig = true;
    let N;
    while ((N = queue.length) > 0) {
        let level = [];
        for (let i = 0; i < N; i++) {
            let node = queue.shift();
            if (node.left != null) queue.push(node.left);
            if (node.right != null) queue.push(node.right);
            if (zig) {
                level.push(node.val);
            } else {
                level.unshift(node.val);
            }
        }
        zig = !zig;
        levels.push(level);
    }
    return levels;
};

• for 문을 이용해서 하나의 shift output에 해당하는 3 결과물만 넣는식으로 코드를 짰더니 시간복잡도 + 메모리가 적게 나오는것을 확인함