109. 有序链表转换二叉搜索树(Convert Sorted List to Binary Search Tree)

来源
描述
题解
- 递归
- 递归 + 转成数组

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

 0<br />    / \<br />  -3   9<br />  /   /<br />-10  5

题解

递归

给定列表中的中间元素将会作为二叉搜索树的根，该点左侧的所有元素递归的去构造左子树，同理右侧的元素构造右子树。这必然能够保证最后构造出的二叉搜索树是平衡的。

/**
 * 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 {

    private ListNode findMiddleElement(ListNode head) {
        // The pointer used to disconnect the left half from the mid node
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;

        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        // Handling the case when slowPtr was equal to head
        if (prevPtr != null) {
            prevPtr.next = null;
        }

        return slowPtr;
    }

    public TreeNode sortedListToBST(ListNode head) {
        // If the head doesn't exist, then the linked list is empty
        if (head == null) {
            return null;
        }

        // Find the middle element for the list
        ListNode mid = this.findMiddleElement(head);

        // The mid becomes the root of the BST
        TreeNode node = new TreeNode(mid.val);

        // when there is just one element in the linked list
        if (head == mid) return node;

        // Recursively form balanced BSTs using the left and right halves of the original list.
        node.left = this.sortedListToBST(head);
        node.right = this.sortedListToBST(mid.next);

        return node;
    }
}

时间复杂度：
空间复杂度：。因为使用递归的方法，所以需要考虑递归栈的空间复杂度。对于一棵非平衡二叉树，可能需要的空间，但是问题描述中要求维护一棵平衡二叉树，所以保证树的高度上界为，因此空间复杂度为。
递归 + 转成数组
空间换时间，将给定的链表转成数组并利用数组来构建二叉搜索树，数组找中间元素只需要的时间，所以会降低整个算法的时间复杂度开销。

/**
 * 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 {
    private List<Integer> values = new ArrayList<>();

    private void mapListToValues(ListNode head) {
        while (head != null) {
            this.values.add(head.val);
            head = head.next;
        }
    }

    private TreeNode convertListToBST(int left, int right) {
        if (left > right) return null;

        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(this.values.get(mid));

        if (left == right) return node;

        node.left = convertListToBST(left, mid - 1);
        node.right = convertListToBST(mid + 1, right);
        return node;
    }

    public TreeNode sortedListToBST(ListNode head) {
        this.mapListToValues(head);
        return convertListToBST(0, this.values.size() -1);
    }
}

复杂度分析

时间复杂度：时间复杂度降到了，因为需要将链表转成数组。而取中间元素的开销变成了，所以整体的时间复杂度降低了。
空间复杂度：因为我们利用额外空间换取了时间复杂度的降低，空间复杂度变成了，相较于之前算法的有所提升，因为创建数组的开销。

来源

描述

题解

递归

递归 + 转成数组