leetcode109.有序链表转换二叉搜索树

题目链接

思路一：链表to数组+递归

我们只需要将链表转换为数组，然后再使用108.将有序数组转换为二叉搜索树的解法即可求解，具体的思路可以参考我的文章。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode root = head;
        while(root != null){
            root = root.next;
            len++;
        }
        int[] nums = new int[len];
        len = 0;
        while(head != null){
            nums[len++] = head.val;
            head = head.next;
        }
        return sortedArrayToBST(nums,0,nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums,int left,int right){
        if(left > right){
            return null;
        }

        int rootIndex = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[rootIndex]);
        root.left = sortedArrayToBST(nums,left,rootIndex - 1);
        root.right = sortedArrayToBST(nums,rootIndex + 1,right);
        return root;
    }
}

时间复杂度：需要将链表的每个节点遍历多次，但是遍历是线性的，所以时间复杂度为O(N)

额外空间复杂度：将链表转换为数组，需要额外的数组空间，同时递归的递归栈深度为O(logN)，所以额外空间复杂度为O(N)

执行结果：

思路二：快慢指针+递归

思路二则是不用额外的数组空间而是使用快慢指针来遍历链表
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        return sortedListToBST(head,null);
    }

    private TreeNode sortedListToBST(ListNode start,ListNode end){
        if(start == end){
            return null;
        }
        ListNode fast = start;
        ListNode slow = start;
        while(fast != end && fast.next != end){
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode newNode = new TreeNode(slow.val);
        newNode.left = sortedListToBST(start,slow);
        newNode.right = sortedListToBST(slow.next,end);
        return newNode;
    }
}

时间复杂度：O(NlogN)
分析如下：
链表的长度为N,对于递归而言，我们使用快慢指针让快指针走到链表末端，慢指针则走到链表中间，也就是说我们对这个长度为N的链表，需要N/2步找到中间元素。接下来，对于每一个递归步骤都是如此，我们可以得到，整体的时间复杂度为：

经简化，该算法的时间复杂度为O(N)。

额外空间复杂度：O(logN)
比起额外使用数组，该算法只需要计算出递归深度即可，因为构建出的二叉树为一棵平衡二叉树，所以深度为logN,额外空间复杂度为O(logN)