【LeetCode 热题 100】108. 将有序数组转换为二叉搜索树

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

整体思路

这段代码旨在解决一个经典的构造性树问题：将有序数组转换为高度平衡的二叉搜索树 (Convert Sorted Array to Binary Search Tree)。目标是利用一个升序排列的数组 nums，构建一棵二叉搜索树（BST），并且这棵树需要是高度平衡的。

该算法采用了递归和分治 (Divide and Conquer) 的思想，这与构建二叉搜索树的性质完美契合。

1. 核心思想：选择根节点

   • 二叉搜索树的性质：左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。
   • 高度平衡：左右两个子树的高度差不超过1。
   • 要同时满足这两个条件，对于一个有序数组 [i...j]，最理想的根节点选择就是数组的中间元素 nums[mid]。
   • 为什么是中间元素？
     • 选择中间元素作为根，数组中它左边的部分 [i...mid-1] 自然就都比它小，可以用来构建左子树。
     • 它右边的部分 [mid+1...j-1] 自然就都比它大，可以用来构建右子树。
     • 由于 mid 将数组近乎平分为两半，递归地用同样的方式构建左右子树，就能确保最终生成的整棵树是高度平衡的。

2. 分治与递归

   • 算法的主体是一个递归函数 dfs(nums, i, j)，它负责将 nums 数组的子区间 [i, j) (左闭右开) 转换为一个平衡BST，并返回该子树的根节点。
   • 递归步骤：
     a. 基本情况 (Base Case)：如果 i == j，表示当前区间为空，没有元素可以构建节点。此时应返回 null，标志着递归的终止。
     b. 分 (Divide)：找到当前区间的中间索引 mid = (i + j) >> 1。
     c. 治 (Conquer)：
     • 创建一个新的 TreeNode，其值为 nums[mid]，这就是当前子树的根节点。
     • 递归构建左子树：调用 dfs(nums, i, mid)，处理 nums 的左半部分 [i, mid)，并将返回的子树根节点连接到当前根节点的 left 指针。
     • 递归构建右子树：调用 dfs(nums, mid + 1, j)，处理 nums 的右半部分 [mid+1, j)，并将返回的子树根节点连接到当前根节点的 right 指针。
       d. 合并 (Combine)：new TreeNode(...) 这行代码本身就完成了合并操作，它将根节点与递归构建好的左右子树连接起来，形成一个完整的子树。
   • 最终，初始调用 dfs(nums, 0, nums.length) 会启动整个递归过程，并返回整棵树的根。

完整代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 将一个升序排列的数组转换为一棵高度平衡的二叉搜索树。
     * @param nums 升序排列的整数数组
     * @return 构建好的高度平衡BST的根节点
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        // 初始调用，处理整个数组区间 [0, nums.length)
        return dfs(nums, 0, nums.length);
    }

    /**
     * 递归辅助函数，用于将数组的子区间 [i, j) 转换为平衡BST。
     * @param nums 输入的原始数组
     * @param i 区间的起始索引（包含）
     * @param j 区间的结束索引（不包含）
     * @return 构建好的子树的根节点
     */
    private TreeNode dfs(int[] nums, int i, int j) {
        // 基本情况：如果起始索引等于结束索引，说明区间为空，返回 null
        if (i == j) {
            return null;
        }
        
        // 找到区间的中间索引。使用位运算 >> 1 等效于 / 2，效率更高，且能避免潜在的溢出问题。
        int mid = (i + j) >> 1;
        
        // 创建当前子树的根节点，其值为中间元素 nums[mid]。
        // 然后递归地构建左子树和右子树：
        //   - 左子树由区间的左半部分 [i, mid) 构建。
        //   - 右子树由区间的右半部分 [mid + 1, j) 构建。
        return new TreeNode(nums[mid], dfs(nums, i, mid), dfs(nums, mid + 1, j));
    }
}

时空复杂度

时间复杂度：O(N)

1. 节点创建：算法为输入数组 nums 中的每一个元素都创建了一个 TreeNode。如果数组长度为 N，那么总共会创建 N 个节点。
2. 递归函数调用：dfs 函数对每个元素调用一次以创建对应的节点。在函数内部，计算 mid 和创建 TreeNode 都是 O(1) 的操作。
3. 综合分析：
   • 每个元素都被访问一次作为 mid，并为其创建一个节点。
   • 因此，总的时间复杂度与数组中元素的数量成正比，为 O(N)。

空间复杂度：O(log N)

1. 主要存储开销：算法的额外空间主要由两部分组成：新创建的树和递归调用栈。
   • 新创建的树：这棵树本身占用了 O(N) 的空间。在一些分析中，这被视为输出，不计入辅助空间。
   • 递归调用栈：这是主要的辅助空间。由于算法每次都选择中间元素作为根节点，它构建的树是高度平衡的。对于一棵包含 N 个节点的高度平衡的树，其高度为 log N。递归的最大深度就等于树的高度。
2. 综合分析：
   • 递归栈的最大深度决定了辅助空间复杂度。因为树是高度平衡的，所以最大深度为 O(log N)。
   • 因此，该算法的（辅助）空间复杂度为 O(log N)。