LeetCode 109 Convert Sorted List to Binary Search Tree 题解

题目链接: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

快慢指针,递归

代码

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

    private ListNode findMid(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode priv = slow;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            priv = slow;
            slow = slow.next;
        }
        priv.next = null;
        return slow;
    }
}

时间复杂度 O(nlogn)

原创文章,作者:ifee,如若转载,请注明出处:https://www.ifee.win/blog/2021/07/25/leetcode-109-convert-sorted-list-to-binary-search-tree-%e9%a2%98%e8%a7%a3/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注