(Leet Code JS) Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Populating Next Right Pointers in Each Node - LeetCode

 

BFS를 이용.

 

BFS에 이용할 queue와 같은 레벨에 있는 노드를 담을 stack을 빈 배열로 선언.

answer = root로 정의.

또 다른 pointer를 root로 지정하고, count는 현재 뎁스의 노드 갯수를 의미한다.

 

만약 루트가 null이라면 바로 root를 리턴하여 예외처리를 한다.

 

그렇지 않다면 queue에 [pointer, 현재 뎁스 = 0]을 push.

while문을 통해 BFS 시작.

 

queue의 맨 앞을 각각 [current, depth] 변수로 받아온다.

또한 current의 자식 노드를 각각 left와 right로 저장한다.

만약 각 자식들이 undefined라면 queue에 담지 않는다.

 

또한 count를 이용해 현재 depth의 노드 갯수를 구할 수 있다.

2 ^ depth는 곧 현재 depth의 노드 갯수를 의미한다.

현재 count가 2 ^ depth가 아니라면 stack에 current를 저장한다.

그렇지 않고 두 수가 같다면 stack에 있는 노드의 정보를 이용해 next를 이어주면 된다.

stack이기 때문에 거꾸로 진행.

 

current.next = null로 지정한 후,

stack을 비워주면서 노드를 이어준다.

node.next = current

current = node로 하여금 노드들을 거꾸로 연결할 수 있다.

const connect = (root) => {
    const answer = root;
    const pointer = root;
    const queue = [];
    const stack = [];
    let count = 1;
    
    if(!root){
        return root;
    }
    
    queue.push([pointer, 0]);
    
    while(queue.length){
        let [current, depth] = queue.shift();
        const left = current.left;
        const right = current.right;
        
        if(left){
            queue.push([left, depth + 1]);
        }
        
        if(right){
            queue.push([right, depth + 1]);    
        }
        
        if(count === Math.pow(2, depth)){
            current.next = null;
            
            while(stack.length){
                const node = stack.pop();
                
                node.next = current;
                current = node;
            }
            
            count = 0;
        } else{
            stack.push(current);
        }
        
        count++;
    }
    
    return answer;
};