【LeetCode 108】算法：将有序数组转换为二叉搜索树

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

平衡二叉搜索树（Balanced Binary Search Tree，常简称 BBST 或 AVL 树）的核心特点：

• 首先是：二叉搜索树
  左子树所有节点值 < 根值 < 右子树所有节点值，中序遍历结果为升序。
  
• 再满足：高度平衡
  对任意节点，左右子树高度差绝对值 ≤ 1，整棵树始终保持近似“满/完全”形态，避免退化成链表。
  
• 因此，操作复杂
  搜索、插入、删除的最坏时间复杂度都为 O(log n)，而非退化时的 O(n)。
  
• 需要动态维护
  每次插入或删除后，通过旋转（单旋、双旋）、变色等规则自动调整，常见实现有 AVL 树、红黑树、Treap、伸展树等。
  

本题的核心思路：
升序数组就是 BST 的中序遍历结果；
每次取 中间元素 作为根节点，再递归左右区间，就能保证整棵树 高度平衡。
复杂度：
时间复杂度：O(n)，每个元素只访问一次
空间复杂度：O(log n)，递归栈深度（平衡树高）
Java 代码实现：

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
17.     public TreeNode sortedArrayToBST(int[] nums) {
19.         if(nums == null) return new TreeNode();
20.         return build(nums, 0, nums.length-1);
21.     }
23.     // 设左右指针为区间边界。注意指针的变化写法。
24.     private TreeNode build(int[] n, int l, int r){
25.         // 递归出口:左指针大于右指针
26.         if(l > r){
27.             return null;
28.         }
29.         // 1、找到父节点
30.         int mid = (l+r)/2;
31.         TreeNode root = new TreeNode(n[mid]);
32.         // 2、在左区间构建左子树
33.         root.left = build(n, l, mid-1);
34.         // 3、在右区间构建右子树
35.         root.right = build(n, mid+1, r);
36.         // 4、返回父节点
37.         return root;
38.     }
39.    
40. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！