[Leetcode] 117. Populating Next Right Pointers in Each Node II - JS

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
next 포인터를 채워서 다음 오른쪽 노드를 가리키도록 한다.
다음 오른쪽 노드가 없으면 null

제한조건
--------------------
- 이진트리의 노드의 갯수는 0 ~ 6000개이다.
- -100 <= Node.val <= 100

 

2. 접근 방법

접근방법 - DFS
--------------------
root에서 시작하여 왼쪽 노드에서부터 오른쪽 노드까지 순회한다. (next로 이동)

current: 현재 레벨의 시작 노드
prev: 이전 노드
nextLevelStart: 다음 레벨이 시작하는 노드

1. 전체 노드를 순회
2. nextLevelStart 기준으로 자식 노드의 next 포인터 연결
	- 왼쪽 노드 먼저 존재 확인
    - 오른쪽 노드 존재 확인
    이 때, current, prev 값 조건에 따라 처리

prev 값이 있으면... prev.next에 할당
prev 값이 없으면... nextLevelStart 갱신
현재 레벨의 노드 연결이 끝나면... current = 다음 레벨의 시작 노드로 이동

 

 

3. 코드

/**
 * // Definition for a _Node.
 * 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;
 * };
 */
var connect = function(root) {
    if (!root) return null;

    let current = root;  // 현재 레벨의 시작 노드

    while (current) {
        let prev = null;   // 이전 노드를 추적
        let nextLevelStart = null;  // 다음 레벨의 시작 노드

        while (current) {
            // 왼쪽 자식 노드가 있으면 연결
            if (current.left) {
                if (prev) {
                    prev.next = current.left;
                } else {
                    nextLevelStart = current.left;
                }
                prev = current.left;
            }

            // 오른쪽 자식 노드가 있으면 연결
            if (current.right) {
                if (prev) {
                    prev.next = current.right;
                } else {
                    nextLevelStart = current.right;
                }
                prev = current.right;
            }

            // 다음 노드로 이동
            current = current.next;
        }

        // 다음 레벨의 시작 노드로 이동
        current = nextLevelStart;
    }

    return root;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

DFS(깊이 우선 탐색) 방법으로 현재 레벨 시작 노드(current)를 기준으로 두고 left(왼쪽 자식 노드), right(오른쪽 자식 노드)의 유무에 따라 자식 노드의 next를 설정해주면서 current(현재 레벨 노드)를 left 노드로 깊이를 증가시켜 나갔다.

 

5. BFS 풀이

BFS(너비 우선 탐색)은 queue 자료구조를 사용하여 구현할 수 있다.

 

var connect = function(root) {
    if (!root) return root;
    
    let queue = [root];
    let tempQueue = [];
        
    while(queue.length){
        let curr = queue.splice(0, 1)[0];
        let {left, right} = curr;
                
        if (left) tempQueue.push(left);
        if (right) tempQueue.push(right);
        
        if (queue.length === 0){
            curr.next = null;
            queue = tempQueue;
            tempQueue = [];
        }else{
            curr.next = queue[0];
        }
    }
    
    return root;
};