LeetCode 114 - Flatten Binary Tree to Linked List (Medium)

문제

LeetCode - 114번

풀이 과정

이진 트리를 연결 리스트로 변경하는 문제입니다.

별도의 메모리를 사용하면 안되기 때문에 dfs 를 응용하여 문제를 해결하였습니다.

루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 연결 리스트로 변경해준 다음
왼쪽 서브트리의 꼬리 노드를 찾아 오른쪽 서브 트리 변환 결과와 연결해줍니다.

이때 루트 노드는 왼쪽 서브트리를 null 로 설정하고 오른쪽 자식을 변형 후의 왼쪽 서브트리와 연결해주면 됩니다.

코드

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  function dfs(root) {
    if (!root) return null;

    const newLeft = dfs(root.left);
    const newRight = dfs(root.right);

    if (newLeft) {
      root.right = newLeft;
      root.left = null;
    }

    let newTail = newLeft;
    while (newTail && newTail.right) {
      newTail = newTail.right;
    }

    if (newTail) newTail.right = newRight;

    return root;
  }

  dfs(root);
};