Flatten Binary Tree to Linked List

---

💬 문제

[문제 링크]

특정 트리의 시작 노드인 root
해당 트리를 preorder로 순회한 순서대로
root에서부터 right로 연결
각 노드에 left는 null이어야 함

✍️ 나의 풀이

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var makeRight = function(node) {
    if (node === null)
        return null;
    node.right = makeRight(node.right);
    node.left = makeRight(node.left);
    if (node.left) {
        let lastNode = node.left;
        while (lastNode.right)
            lastNode = lastNode.right;
        lastNode.right = node.right;
        node.right = node.left;
        node.left = null;
    }
    return node;
}

var flatten = function(root) {
    if (root === null)
        return ;
    root = makeRight(root);
};

재귀함수를 사용하여 구현
각 노드를 기준으로 오른편 먼저 직선으로 정리한 후
왼편도 정리하여 오른쪽으로 삽입하는 과정을 반복
따라서 가장 아래쪽에서부터 정리하면서 올라오는 형태
오른쪽으로 삽입할 때, 정리된 왼편 트리의 마지막 노드를 알아야하므로
lastNode를 선언하여 끝까지 이동시켜서 사용
마지막으로, 주어진 함수의 반환값이 없으므로 완성된 트리로 기존의 root를 대체

📌 결과

Accepted
Runtime 63ms (Beats 79.09%)
Memory 52.59MB (Beats 47.39%)

📚 러닝 포인트

나는 밑에서부터 정리하면서 올라오는 형식으로 구현을 했는데, 다 하고 나서 솔루션을 둘러보니 훨씬 간단하게 내려가면서 정리할 수 있는 방법도 있었다.

var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            let last = curr.left;
            while (last.right)
                last = last.right;
            last.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};

오른쪽으로 내려가면서 현재 노드가 왼쪽 자식을 갖고 있다면 해당 서브트리를 그대로 오른쪽 자식으로 삽입한다. 아직 정렬되지 않은 부분은 오른쪽으로 내려가면서 하나씩 정리되는 방식이다. 따로 재귀 함수를 활용하지 않아도 되서 좋은 것 같다. 나도 이렇게 간편한 코드를 언젠간 뚝딱 만들 수 있겠지?