力扣 - 109. 有序链表转换为二叉搜索树

题目

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

思路

• 二叉搜索树就是左孩子比根节点小，右孩子比根节点大，而且左右两个子树的高度差不大于1称为二叉搜索树
• 通过观察这个链表转换成的搜索树可以发现，根节点其实就是链表的中间的结点，左孩子就是左边一半链表的中间的结点，右孩子就是右边一半链表的中间的结点
• 所以可以利用递归（自顶向下）方法来解题，递归的截止条件就是遍历到本段链表末尾

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;

        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);

        return root;
    }
}

复杂度分析

• 时间复杂度：\(O(NlogN)\)，其中 N 为链表的长度。
• 空间复杂度：\(O(logN)\)，其中logN为树的深度，递归时所创建的空间

力扣 - 109. 有序链表转换为二叉搜索树

原文：https://www.cnblogs.com/linzedian/p/13951956.html