☆打卡算法☆LeetCode 109、有序链表转换二叉搜索树 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定单链表头结点，其中元素升序排序，将其转换为高度平衡的二叉搜索树。”

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

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

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

示例 1：
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2：
输入: head = []
输出: []

二、解题

1、思路分析

这道题跟108题类似，第一步都是需要确定根节点，也就是让左右子树的节点个数尽可能接近，这样左右子树的高度就会相近。

这样的根节点被称为中位数，如果链表的元素个数为奇数，那么中间值就位中位数，如果元素个数为偶数，那么两个中间值都可以作为中位数。

根据中位数的性质，可以使用分治的思路，递归地对左右子树进行构造，找出对应的中位数作为根节点，这样得到的二叉搜索树就是平衡的。

2、代码实现

代码参考：

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

3、时间复杂度

时间复杂度 ： O(n log n)

其中n是链表的长度。

空间复杂度： O(log n)

其中n是数组的长度，空间复杂度取决于递归栈的深度，递归栈的深度是O(log n)。

三、总结

找出链表中位数节点的方法有很多，比较简单的是使用双指针，在开始时候两个指针都指向左端点left。

然后第一个指针向右移动两次的同时第二个指针向右移动一次，直到第一个指针到达边界的时候，第二个指针对应的元素就是中位数。

找到中位数之后，将其作为当前根节点的元素，然后递归地构造其左侧部分的链表对应的左子树，以及右侧部分的链表对应的右子树。