108. 将有序数组转换为二叉搜索树

;(function () {
  /**
   * 108. 将有序数组转换为二叉搜索树
   * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
   *
   * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
   *
   * 输入：nums = [-10,-3,0,5,9]
   * 输出：[0,-3,9,-10,null,5]
   * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
   *
   */

  class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
      this.val = val === undefined ? 0 : val
      this.left = left === undefined ? null : left
      this.right = right === undefined ? null : right
    }
  }

  // 二叉搜索树 通过【中序遍历】能得到 有序数组
  // 当前题目：属于反向操作
  function sortedArrayToBST(nums: number[]): TreeNode | null {
    // 方法一：
    function helper(nums: number[], left: number, right: number) {
      if (left > right) return null
      // 这里可以选择最中间靠左或者靠右的某个下标
      let mid = Math.floor((left + right) / 2)
      // 根节点
      let root: TreeNode | null = new TreeNode(nums[mid])
      root.left = helper(nums, left, mid - 1)
      root.right = helper(nums, mid + 1, right)
      return root
    }
    return helper(nums, 0, nums.length - 1)

    // // to right
    // let beforeTree: TreeNode | null = root;
    // for (let i = mid + 1; i < len; i++) {
    //     let curTree = new TreeNode(nums[i])
    //     beforeTree.right = curTree
    //     beforeTree = curTree
    // }
    // // to left
    // let afterTree: TreeNode | null = root;
    // for (let i = mid - 1; i >= 0; i--) {
    //     let curTree = new TreeNode(nums[i])
    //     afterTree.left = curTree
    //     afterTree = curTree
    // }
  }

  let nums = [-10, -3, 0, 5, 9] // [0,-3,9,-10,null,5]
  sortedArrayToBST(nums)
})()