简述Java如何有序链表重建 BST/AVL ？

要将有序链表重建为平衡二叉搜索树（BST）或AVL树，我们可以使用递归的方法。这里我们主要关注BST的重建，因为AVL树是BST的一种，它在每次插入或删除节点后都会进行自我平衡。

以下是一个简单的步骤说明，以及如何使用Java实现这个过程：

步骤

1. 找到链表的中间节点：由于给定的链表是有序的，我们可以使用快慢指针技巧来找到链表的中间节点。这个中间节点将是我们的BST的根。
2. 递归地构建左子树和右子树：使用中间节点将链表分为两部分，然后递归地为左半部分和右半部分执行相同的操作，从而得到左子树和右子树。
3. 将左子树、根和右子树组合起来：将左子树、根和右子树组合起来，形成一个BST。

Java实现

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        
        // 使用快慢指针找到中间节点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 创建根节点
        TreeNode root = new TreeNode(slow.val);
        
        // 递归构建左子树和右子树
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        
        return root;
    }
}

注意：上述代码只构建了BST，并没有处理AVL树的自平衡操作。如果要构建AVL树，你需要在每次插入或删除节点后都执行自平衡操作，确保树的高度差不超过1。这涉及到旋转和平衡操作，相对复杂一些。