LeetCode刷题实战109：有序链表转换二叉搜索树-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 有序链表转换二叉搜索树，我们先来看题面：

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

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题意

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

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

样例

解题

因为链表是有序的，我们递归时每次把中间的数加为节点进行构造二叉树就可以了，这个每次找链表的中间节点依旧可以使用快慢指针的方法进行找。找中间节点和构造二叉树便是此题的重点啦，找中间的节点也可以使用数组，就是把链表的数据都存到数组中，然后每次找中间的节点。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return createTree(head, null);
    }
    public TreeNode createTree(ListNode head, ListNode tail) {
        if(head == tail ) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode node = new TreeNode(slow.val);
        node.left = createTree(head, slow);
        node.right = createTree(slow.next, tail);
        return node;
    } 
}