Populating Next Right Pointers in Each Node - BFS 알고리즘

Populating Next Right Pointers in Each Node - LeetCode

문제

완벽 이진 트리(Perfect Binay tree)의 노드들이
같은 레벨의 오른쪽 노드의 포인터를 가질 수 있게 하라

---

문제 해결 방안

한 레벨별로 생각을 한다.

각 레벨을 Queue에 넣게 되면, Queue의 오른쪽 아이템은 내 오른쪽 노드가 된다.

레벨 3이 Queue에 있다면, [4, 5, 6, 7]과 같이 된다.

그렇다면 queue[0]의 right는 queue[1]이 되는 식이다.

 

주의할 점

일반 BFS와 같이 진행을 하게 되면 3의 오른쪽 노드가 null이 아니라 4가 된다.

왜냐하면 Queue: [2, 3]상태였다가 2의 자식 4, 5를 추가하면서

Queue: [3, 4, 5]와 같이 되기 때문이다.

그렇기 때문에 각 레벨단위로 끊어서 계산을 해 줄 것이다.

---

코드 (TypeScript)

function connect(root: Node | null): Node | null {
    let queue = [root];
    // length: node count of current level
    let length = queue.length;
    
    while (length > 0) {
        for (let i = 0; i < length; i++) {
            let node = queue.shift();

            if (node === null) {
                continue;
            }

			// last item's right is null.
            let next = i === length - 1 ? null : queue[0];
            node.next = next;

			// insert left and right
            queue.push(node.left);
            queue.push(node.right);
        }
        
        // reset length of this level
        length = queue.length;
    }
    
    return root;
};