有序链表转换二叉搜索树

[louzhedong]

习题

出处 LeetCode 算法第109题

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

思路

高度平衡二叉树每一个节点的左子树和右子树的节点的个数相差不超过1，所以我们可以先将链表转换成数组，从数组中间将数组分成两个子数组。再采用递归的方式，即可得到完整的树

解答

function ListNode(val) {
  this.val = val;
  this.next = null;
}

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

function helper(array) {
  if (array.length === 0) {
    return null;
  }
  var length = array.length;
  var index = Math.floor(length / 2);
  var root = new TreeNode(array[index]);
  root.left = helper(array.slice(0, index));
  root.right = helper(array.slice(index + 1));
  return root;
}
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head) {
  var array = [];
  while (head && head.val !== undefined) {
    array.push(head.val);
    head = head.next;
  }
  if (array.length == 0) {
    return [];
  }
  return helper(array);
};

var head = first = new ListNode(-10);
first.next = new ListNode(-3);
first = first.next;
first.next = new ListNode(0);
first = first.next;
first.next = new ListNode(5);
first = first.next;
first.next = new ListNode(9);
first = first.next;
console.log(sortedListToBST(head));