前端算法leetcode109题解有序链表转换二叉搜索树

前端算法leetcode109题解-有序链表转换二叉搜索树

题目描述

给定一个单链表 L： L0→L1→…→Ln-1→Ln ，将其转换为二叉搜索树。

示例 1:

输入: [-10,-3,0,5,9]
输出: 与示例二叉树相同
     0
    / \
  -3   9
  /   /
-10  5

示例 2:

输入: [1,2,3,4,5,6,7]
输出: 与示例二叉树相同
        4
       / \
      2   6
     / \ / \
    1  3 5  7

解题思路

这是一道 AC 的比较难的题目，我们需要通过转化，修改题目的表述，直到我们熟悉这样的题目。

一般情况下我们是有序数组变成二叉搜索树

这是一张有序数组变成的二叉搜索树：

        4
       / \
      2   6
     / \ / \
    1  3 5  7

如果数组是有序的：

[1, 2, 3, 4, 5, 6, 7]

我们可以找到中间唯一的节点 4，那么我们就可以分别递归的生成 左右子树。

生成 2 的左子树 [1, 2, 3]
生成 6 的右子树 [5, 6, 7]

当数组中的元素只剩下一个时，就生成了该节点！由于数组是有序数组，那么每次取中间节点的时间复杂度是 O(1)。总体时间复杂度是 O(nlog(n))。

将上面的有序数组修改成链表

这个只要在每个节点多记录一个 parent 节点就 OJBK 了， 也就是修改了链表的实现，由原来的数组实现，修改为链表实现，其他递归的操作与前面一样。

不用每次都遍历 half 部分的链表，直接递归：左-根-右

这个 comparator 跟上一次不太一样，上一个的比较是 < ，代表哪边大，哪边继续搜索比较；这次的比较是 > ，代表哪边小，哪边继续搜索比较。

代码实现

/*
 * 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;
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */

const formOrderedList = head => {
    let length = 0;
    let node = head;
    while (node !== null) {
        length++;
        node = node.next;
    }
    const array = new Array(length);
    let i = 0;
    node = head;
    while (node !== null) {
        array[i++] = node.val;
        node = node.next;
    }
    return arrayToBST(array, 0, length - 1);
};

const arrayToBST = (array, start, end) => {
    if (start > end) {
        return null;
    }

    const middleIndex = Math.floor((start + end) / 2);
    const node = new TreeNode(array[middleIndex]);
    node.left = arrayToBST(array, start, middleIndex - 1);
    node.right = arrayToBST(array, middleIndex + 1, end);

    return node;
};