Populating Next Right Pointers in Each Node II

---

💬 문제

[문제 링크]

특정 트리의 시작 노드인 root
노드마다 next 속성을 가지고 있으며 null로 초기화되어 있음
각 노드의 오른쪽(같은 level) 노드를 next에 할당
가장 오른편에 있는 노드의 next는 null로 하여
다시 root 노드를 반환

✍️ 나의 풀이

/**
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function(root) {
    let queue = [root];

    while (queue[0]) {
        let cnt = queue.length;
        let node;

        for (let i = 0; i < cnt; i++) {
            node = queue.shift();
            node.next = queue[0];
            if (node.left)
                queue.push(node.left);
            if (node.right)
                queue.push(node.right);
        }
        node.next = null;
    }

    return root;
};

queue를 사용하여 BFS 구현
depth를 확인했던 문제와 같이 한 level씩 처리하기 위하여 for문 사용
해당 level의 마지막 노드는 next가 null이어야 하므로 for문이 끝나면 다시 할당
queue가 빌 때까지 진행하면 모두 다 확인한 것이므로 그대로 root 반환

📌 결과

Accepted
Runtime 67ms (Beats 58.20%)
Memory 53.99MB (Beats 39.90%)

📚 러닝 포인트

BFS로 풀 때는 이미 depth별로 체크하는 알고리즘을 구현해본 적이 있어서 어렵지 않게 작성했다. 그러나 문제의 도전과제가 You may only use constant extra space였는데, BFS로는 queue를 사용하고 있어서 DFS로도 구현을 해봤다.

var findNext = function(node) {
    node = node.next;
    while (node) {
        if (node.left)
            return node.left;
        if (node.right)
            return node.right;
        node = node.next;
    }
    return null;
}

var connect = function(root) {
    if (root === null)
        return root;
    if (root.left)
        root.left.next = root.right ? root.right : findNext(root);
    if (root.right)
        root.right.next = findNext(root);

    connect(root.right);
    connect(root.left);

    return root;
};

현재 노드를 기준으로 자식들의 next를 이어주고 다음 자식으로 넘어가는 방식이다. 따라서 자식의 next를 구해줄 때, 기준 노드의 next를 찾아가서 그 노드의 자식을 연결해준다. 이 때 주의해야할 점은 오른쪽 트리를 먼저 완성하는 것이다. 보통은 DFS를 돌릴 때 왼쪽을 완료한 후에 오른쪽으로 가지만, 이 문제에서는 오른쪽 구역에 자식이 없는 노드가 있다면 왼쪽 구역의 노드가 next가 없다고 판단하여 끊겨버리는 상황이 발생할 수 있기 때문이다.