[LeetCode] 114. Flatten Binary Tree to Linked List

😎풀이

Binary Tree를 Linked List로 변환하는 문제이다.

Linked List는 left를 갖지 않는다는 명시가 있는점을 참고해야함

전위 순회를 기준으로 연결해야 하기에 leftSubTree가 우선적으로 오며 이후 leftSubTree의 끝에서 rightSubTree가 연결되는 구조로 작업하면 된다.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/**
 Do not return anything, modify root in-place instead.
 */
function flatten(root: TreeNode | null): void {
    if(!root) return null

    // 좌, 우 subTree 분리
    const leftSubTree = root.left
    const rightSubTree = root.right

    // 좌측 트리 제거(문제 요구사항)
    root.left = null

    // 전위 순회이므로 leftSubTree부터 flatten
    flatten(leftSubTree)
    flatten(rightSubTree)

    // 우측 방향을 flatten된 leftSubTree로 설정
    root.right = leftSubTree

    // 설정된 leftSubTree의 끝 부분에 rightSubTree 연결
    let current = root
    while(current.right) {
        current = current.right
    }
    current.right = rightSubTree
};