【基础篇 - Day 9】 2020-11-09 - 109. 有序链表转换二叉搜索树（02. 链表 ）

题目描述

入选理由

1. 考察大家对指针的处理，如避免环的产生。
2. 本题也很适合使用递归进行处理，大家可以用它来练习链表的递归（前后序）。
3. 考察大家对快慢指针的了解程度。

题目链接

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

题目描述

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

平衡二叉树 根据中心点去构造一棵树

var sortedListToBST = function (head) {
    if (!head) return null
    let arr = []
    while (head) {
        arr.push(head.val)
        head = head.next
    }
    function buildTree(start, end) {
        if (start > end) return null
        const mid = Math.ceil(start + (end - start) / 2)
        const root = new TreeNode(arr[mid])
        root.left = buildTree(start, mid - 1)
        root.right = buildTree(mid + 1, end)
        return root
    }
    return buildTree(0, arr.length - 1)
};

解法二

时间复杂度：O(n)

空间复杂度: O(1)

双指针法 通过快指针走完之后慢指针正好处在中心点，接下来递归即可

var sortedListToBST = function (head) {
    if (!head) return null
    let slow = head
    let fast = head
    let preSlow
    while (fast && fast.next) {
        preSlow = slow
        slow = slow.next
        fast = fast.next.next
    }
    const root = new TreeNode(slow.val)
    if (preSlow!=null) {
        preSlow.next = null
        root.left = sortedListToBST(head)
    }
    root.right = sortedListToBST(slow.next)
    return root
};

参考回答

• 官方题解 (opens new window)