#yyds干货盘点# LeetCode程序员面试金典：有序链表转换二叉搜索树

题目：

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

在这个问题中，一棵高度平衡的二叉树是指两棵子树的高度差不超过一棵二叉树的每个节点 1。

示例 1:

输入: head = [-10，-3，0，5，9]

输出: [0,-3,9,-10,null,5]

解释: 可能的答案是[0，-3，9，-10，null,5]它表示高度平衡的二叉搜索树。

示例 2:

输入: head = []

输出: []

代码实现：

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;    }}