[Leetcode] 114. Flatten Binary Tree to Linked List - JS

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 평탄화하라.
right 포인터가 다음 노드를 가리킨다. left 자식은 항상 null이다.
순서는 전위순회(부모 -> left -> right)와 동일해야한다.
아무것도 반환하지말고 제자리에서 평탄화하라.


제한조건
--------------------
- 노드의 갯수는 0 ~ 2000이다.
- -100 <= Node.val <= 100

 

2. 접근 방법

접근방법
--------------------
1. 모든 노드 순회(current)

2. 왼쪽 자식 노드가 존재하면
- 왼쪽 자식 노드의 오른쪽 최하단 노드를 current.right와 연결해준다.
- 현재 노드의 왼쪽 자식을 오른쪽 자식으로 할당한다.

3. current를 current 오른쪽 자식으로 이동한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var flatten = function(root) {
    if (!root) {
        return null;
    }

    let current = root;

    while (current) {
        if (current.left) {
            let rightMost = current.left;
            while (rightMost.right) {
                rightMost = rightMost.right;
            }
            rightMost.right = current.right;
            current.right = current.left;
            current.left = null;
        }
        current = current.right;
    }
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

현재 왼쪽 자식 노드의 최하단 오른쪽 자식의 오른쪽 자식으로 현재 오른쪽 자식 노드와 연결하는 것이 인상 깊었다.

마치 화학 구조물을 이리 저리 옮기는 것 같았다.

 

맨 처음에는 전위 순회를 위해 재귀방법을 사용하였으나, 재귀 방법 보다 while 반복문을 사용하는 것이 더 이해가 쉬웠다.

재귀가 쉬운 방법, 반복문이 쉬운 방법이 각각 있는 것 같다.

 

GPT랑 함께 공부한 결과이므로 여러번 반복해서 풀면서 익숙해져야겠다.