Lstmxx的空间

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

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

链接

function sortedArrayToBST(nums: number[]): TreeNode | null {
  if (nums.length === 0) return null
  return traverse(nums, 0, nums.length - 1)
};

function traverse(inorder: number[], inStart: number, inEnd: number): TreeNode | null {
  if (inStart > inEnd) return null
  const midIndex = Math.floor((inEnd - inStart) / 2) + inStart
  const rootVal = inorder[midIndex]
  const root = new TreeNode(rootVal)
  const left = traverse(inorder, inStart, midIndex - 1)
  const right = traverse(inorder, midIndex + 1, inEnd)
  root.left = left
  root.right = right
  return root
}