一天一大 lee(有序链表转换二叉搜索树)难度:中等-Day20200818

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 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 {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head) {
  let nums = []
  while (head) {
    nums.push(head.val)
    head = head.next
  }
  return build(nums, 0, nums.length - 1)
  function build(nums, left, right) {
    if (left > right) return null
    let mid = parseInt((left + right) / 2, 10)
    let node = new TreeNode(nums[mid])
    node.left = build(nums, left, mid - 1)
    node.right = build(nums, mid + 1, right)
    return node
  }
}

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head) {
  return build(head, null)
  function build(left, right) {
    if (left === right) return null
    let mid = getMedian(left, right)
    let node = new TreeNode(mid.val)
    node.left = build(left, mid)
    node.right = build(mid.next, right)
    return node
  }

  function getMedian(left, right) {
    let fast = left,
      slow = left
    while (fast != right && fast.next != right) {
      fast = fast.next
      fast = fast.next
      slow = slow.next
    }
    return slow
  }
}

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head) {
  let globalHead = head,
    len = getLength(head)
  return build(0, len - 1)

  function getLength(head) {
    let i = 0
    while (head != null) {
      ++i
      head = head.next
    }
    return i
  }

  function build(left, right) {
    if (left > right) return null
    let mid = parseInt((left + right + 1) / 2, 10)
    let node = new TreeNode()
    node.left = build(left, mid - 1)
    node.val = globalHead.val
    globalHead = globalHead.next
    node.right = build(mid + 1, right)
    return node
  }
}