Lstmxx的空间

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

链接

/**
 * 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 findMid(left: ListNode, right: ListNode): ListNode {
  let slow = left
  let fast = left
  while(fast !== right && fast.next !== right) {
    fast = fast.next
    fast = fast.next
    slow = slow.next
  }
  return slow
}
function dfs(left: ListNode, right: ListNode): TreeNode | null {
  if (left === right) return null
  const middle = findMid(left, right)
  const root = new TreeNode(middle.val)
  root.left = dfs(left, middle)
  root.right = dfs(middle.next, right)
  return root
}
function sortedListToBST(head: ListNode | null): TreeNode | null {
  return dfs(head, null);
};