Java算法题-解析 将排序链表转换为二叉搜索树 算法问题

题目：

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

引言：

二叉搜索树（BST）是一种常见的二叉树类型，它的特点是对于每个节点，其左子树中的值都小于等于该节点的值，而右子树中的值都大于等于该节点的值。平衡二叉搜索树是一种特殊的BST，它的左右子树高度差不超过1，这保证了树的查找和插入操作的平均时间复杂度为O(log n)。

将一个排序链表转换为平衡BST是一个有趣的问题，解决这个问题需要找到链表的中间节点作为树的根节点，然后递归地构建左子树和右子树。

算法思路：

1. 使用快慢指针法找到链表的中间节点，中间节点将成为树的根节点。
2. 递归地将左半部分链表构建为左子树，将右半部分链表构建为右子树。
3. 返回根节点。

代码实现：

以下是使用 Java 实现的解决方案：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class ConvertSortedListToBST {
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        if (prev != null) {
            prev.next = null;
        }

        return slow;
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode middle = findMiddle(head);
        TreeNode root = new TreeNode(middle.val);

        if (middle == head) {
            return root;
        }

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(middle.next);

        return root;
    }

    public static void main(String[] args) {
        ConvertSortedListToBST solution = new ConvertSortedListToBST();

        // 示例输入：升序排序的链表
        ListNode head = new ListNode(-10);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);

        TreeNode root = solution.sortedListToBST(head);

        System.out.println("转换后的二叉搜索树的中序遍历结果:");
        inOrderTraversal(root);
    }

    private static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }
}

算法分析：

• 时间复杂度：构建平衡BST的时间复杂度是O(n)，其中n是链表的长度。
• 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(log n)。

示例和测试：

假设给定升序排序的链表 head，如下所示：

head = [-10, -3, 0, 5, 9]

根据算法，我们将得到以下平衡BST：

     0
    / \
  -3   9
  /   /
-10  5

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        ConvertSortedListToBST solution = new ConvertSortedListToBST();

        ListNode head = new ListNode(-10);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);

        TreeNode root = solution.sortedListToBST(head);

        System.out.println("转换后的二叉搜索树的中序遍历结果:");
        inOrderTraversal(root);
    }

    private static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }
}

总结：

将升序排序的链表转换为平衡的二叉搜索树是一个有趣的问题，通过找到链表的中间节点，然后递归地构建左子树和右子树，我们可以有效地解决这个问题。这个算法的时间复杂度是O(n)，空间复杂度是O(log n)，其中n是链表的长度。解决这个问题有助于加深对二叉搜索树的理解，以及对递归构建树结构的能力。