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

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

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

二、解题

1、思路分析

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

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

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

2、代码实现

代码参考：

代码语言：javascript复制

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 &amp;&amp; fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}