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

题目描述

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

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

示例:

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

来源：LeetCode

思路

递归+二叉树。给出的链表已经是有序的了，需要建一棵平衡树，显然需要取中间的节点为根建树，然后左边又是一个有序链表，同样建树作为左子树，右边同理。

需要注意几点。一是找到中间节点后，要将左边链表切断。二是注意处理边界情况，否则很可能陷入死循环。

解法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

const getMiddle = head => {
  let middle = head;
  let tail = head;
  let preMiddle = head;

  while (tail && tail.next) {
    preMiddle = middle;
    middle = middle.next;
    tail = tail.next.next;
  }

  // 切断链表
  preMiddle.next = null;

  return middle;
};

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  if (!head) return null;

  const middle = getMiddle(head);
  const root = new TreeNode(middle.val);

  if (head !== middle) {
    root.left = sortedListToBST(head);
  }

  root.right = sortedListToBST(middle.next);

  return root;
};