BST 构造：从有序数组建树

将有序数组转换为二叉搜索树（LeetCode 108）

分治：取中间元素为根，递归构建左右子树（自然是高度平衡的）：

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = build(nums, lo, mid - 1);
    node.right = build(nums, mid + 1, hi);
    return node;
}

有序链表转换二叉搜索树（LeetCode 109）

用快慢指针找链表中点，分治构建：

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        prev = slow; slow = slow.next; fast = fast.next.next;
    }
    prev.next = null;  // 断开左半部分
    TreeNode node = new TreeNode(slow.val);
    node.left = sortedListToBST(head);
    node.right = sortedListToBST(slow.next);
    return node;
}

将 BST 转换为更大树（LeetCode 538）

每个节点值 ← 原值 + 所有更大节点值之和。**逆中序遍历（右→根→左）**并累加：

private int sum = 0;
public TreeNode convertBST(TreeNode root) {
    if (root != null) {
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
    }
    return root;
}

BST 转双向循环链表（变体题）

中序遍历，维护 prev 指针，连接当前节点与 prev，最后头尾相连：

private TreeNode prev = null, head = null;
public TreeNode treeToDoublyList(TreeNode root) {
    if (root == null) return null;
    inorder(root);
    head.left = prev; prev.right = head;
    return head;
}
private void inorder(TreeNode cur) {
    if (cur == null) return;
    inorder(cur.left);
    if (prev != null) prev.right = cur;
    else head = cur;
    cur.left = prev;
    prev = cur;
    inorder(cur.right);
}

总结