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

链接：109.有序链表转换二叉搜索树
难度：Medium
标签：树、二叉搜索树、链表、分治、二叉树
简介：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

题解 1 - typescript

• 编辑时间：2020-08-18
• 执行用时：96ms
• 内存消耗：46.7MB
• 编程语言：typescript
• 解法介绍：通过有序数组进行深度遍历。

function sortedListToBST(head: ListNode | null): TreeNode | null {
  if (head === null) return null;
  const arr: number[] = [];
  while (head !== null) {
    arr.push(head.val);
    head = head.next;
  }
  return toBST(arr);
  function toBST(array: number[]): TreeNode | null {
    const len = array.length;
    if (len === 0) return null;
    const mid = len >> 1;
    const node = new TreeNode(
      array[mid],
      toBST(array.slice(0, mid)),
      toBST(array.slice(mid + 1, len))
    );
    return node;
  }
}