[LeetCode] 109. Convert Sorted List to Binary Search Tree

😎풀이

linked list를 tree node로 변환하며 중요점은 가운데 값을 찾기 위해 세개의 포인터를 두고 이동해가며 중간에 존재할 루트 노드를 찾는 과정이다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 * 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)
 *     }
 * }
 */

function sortedListToBST(head: ListNode | null): TreeNode | null {
    // 빈 링크드 리스트인 경우 null 반환
    if (!head) return null;
    // 단일 노드인 경우 해당 값을 가진 트리 노드 반환
    if (!head.next) return new TreeNode(head.val);
    
    // 빠른 포인터와 느린 포인터를 사용하여 중간 노드를 탐색
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    let prev: ListNode | null = null;
    
    // fast가 리스트 끝에 도달할 때까지 이동
    // slow는 중간 지점에 도달
    while (fast && fast.next) {
        fast = fast.next.next;
        prev = slow;
        slow = slow!.next;
    }
    
    // 중간 노드를 기준으로 리스트 분할
    if (prev) prev.next = null;
    
    // 중간 값으로 새로운 트리 노드 생성
    const root = new TreeNode(slow!.val);
    
    // 중간 노드를 기준으로 왼쪽과 오른쪽 서브트리를 재귀적으로 구성
    // head가 리스트의 시작점이 되고, slow.next가 오른쪽 부분의 시작점이 됨
    root.left = head === slow ? null : sortedListToBST(head);
    root.right = sortedListToBST(slow!.next);
    
    return root;
}