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

ps 图灵课堂老师从近一百套最新一线互联网公司面试题中精选而出，涵盖Java架构面试 所有技术栈，包括JVM，Mysql，并发，Spring，Redis，MQ，Zookeeper，Netty， Dubbo，Spring Boot，Spring Cloud，数据结构与算法，设计模式等相关技术领域的大 厂面试题及详解。 详情咨询客服获取全套面经试题。