108.Convert_Sorted_Array_to_Binary_Search_Tree

/**
 * 将有序数组转换为高度平衡的二叉搜索树
 * 平衡二叉搜索树的定义：每个节点的左右两个子树的高度差的绝对值不超过 1
 * 二叉搜索树的特性：左子树所有节点值 < 根节点值 < 右子树所有节点值
 * @param {number[]} nums - 升序排列的整数数组
 * @returns {TreeNode} - 平衡二叉搜索树的根节点
 */
var sortedArrayToBST = function (nums) {
  /**
   * 深度优先递归函数，构建平衡二叉搜索树
   * @param {number} left - 当前子数组的左边界（包含）
   * @param {number} right - 当前子数组的右边界（不包含）
   * @returns {TreeNode|null} - 构建好的子树的根节点，无元素时返回null
   */
  function dfs(left, right) {
    // 递归终止条件：当左边界等于右边界时，说明当前子数组为空，返回null
    if (left === right) {
      return null
    }

    // 计算当前子数组的中间索引，取整避免小数
    // 选择中间元素作为根节点，能保证左右子树的节点数量尽可能均衡
    const mid = Math.floor((left + right) / 2)

    // 构建当前节点：
    // 1. 节点值为数组中间位置的元素
    // 2. 左子树由左半部分子数组 [left, mid) 递归构建
    // 3. 右子树由右半部分子数组 [mid+1, right) 递归构建
    return new TreeNode(
      nums[mid], // 当前节点的值
      dfs(left, mid), // 递归构建左子树
      dfs(mid + 1, right), // 递归构建右子树
    )
  }

  // 初始调用递归函数，处理整个数组 [0, nums.length)
  return dfs(0, nums.length)
}