LeetCode Flatten Binary Tree to Linked List in Javascript

문제

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

접근

문제에서 따로 정렬된 트리를 리턴할 필요가 없이 root 트리를 재 정렬하도록 하게 되어 있다. 기본적인 풀이 방법은 DFS를 사용하면 되는데 DFS는 Stack를 이용하므로 Stack을 통해 DFS 순서에 맞게 노드를 하나씩 집어넣고 뒤에서부터 꺼내서 노드를 달아주면 된다.

정답 코드는 아래와 같다.

var flatten = function(root) {
    if(!root) return;
    
    const stack = new Array();
    stack.push(root);
    
    while(stack.length){
        // 1
        const curr = stack.pop();
        
        // 2
        if(curr.right){
            stack.push(curr.right);
        }
       
        if(curr.left){
            stack.push(curr.left);
        }
        
        // 3
        if(stack.length){
            curr.right = stack[stack.length-1];
        }
        
        // 4
        curr.left = null;
    }
};

먼저 스택을 선언하고 root를 넣어준다. 그리고 stack에 원소가 존재하는 동안 while문을 돌려주는데,

1. 먼저 stack에서 하나 꺼내서 현재 노드를 표시해준다.
2. 현재 노드의 오른쪽 먼저 넣고 왼쪽을 넣어준다. 이렇게 하면 다음 while문의 순서에서 DFS의 순서를 따라가게 된다.
3. 현재 노드의 오른쪽에 현재 노드의 왼쪽 값 또는 없다면 부모 노드의 오른쪽 값을 넣는다.
4. 왼쪽 값을 null로 없애 주어 편향된 트리를 만들어준다.

이런 순서로 진행이 된다.