(Leet Code JS)Flatten a Multilevel Doubled Linked List

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

Flatten a Multilevel Doubly Linked List - LeetCode

주어진 양방향 리스트를 평탄화를 하여 리턴해야 한다.

 

우선 예외처리로 head가 비어있다면 그대로 비어있는 head를 리턴한다.

그렇지 않다면 DFS로 모든 노드를 배열에 담아주도록 한다.

담는 순서는 현재 방문한 노드 -> 자식 노드 -> 같은 레벨의 노드 다.

 

dfs.

노드를 매개 변수로 받아온다.

arr 배열에는 new Node(node.val)로 노드를 새로 생성하여 넣어준다.

이후 노드의 자식 노드를 확인하여 dfs를 계속 진행.

자식 노드의 탐색이 끝나면 형제 노드를 탐색한다.

 

dfs가 끝나면 arr을 순회하여 평탄화 작업을 한다.

answer를 우선 arr[0]으로 저장하고 시작.

i < arr.length - 1 이라면 arr[i].next = arr[i + 1] 로 지정.

i > 0 이라면 arr[i].prev = arr[i - 1]로 지정.

 

for문을 통해 양방향 리스트로 평탄화 작업을 할 수 있으며,

answer를 리턴하면 된다.

var flatten = function(head) {
    const arr = [];
    let current = head;
    let answer;
    
    const dfs = (node) => {
        arr.push(new Node(node.val));
        
        if(node.child !== null){
            dfs(node.child);
        }
        
        if(node.next !== null){
            dfs(node.next);
        }
    }
    
    if(!head){
        return head;
    }
    
    dfs(current);
    
    answer = arr[0];
    
    for(let i = 0; i < arr.length; i++){
        if(i < arr.length - 1){
            arr[i].next = arr[i + 1]; 
        }
        
        if(i > 0){
            arr[i].prev = arr[i - 1];
        }
    }
    
    return answer;
};