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

/*
 * @lc app=leetcode.cn id=108 lang=typescript
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * 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)
 *     }
 * }
 */

/**
 * 二叉搜索树：左子树所有节点都小于该节点，右子树都大于该节点
 *
 *
 *
 * */

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 {
	if (!nums.length) return null;
	return useRecursion(nums, 0, nums.length - 1);
}

function useRecursion(nums: number[], l: number, r: number): TreeNode | null {
	if (l > r) {
		return null;
	}
	let mid = l + +Math.floor((r - l) / 2);
	let middle = nums[mid]; // 向下取整
    
	const node = new TreeNode(middle);

	node.left = useRecursion(nums, l, mid - 1);
	node.right = useRecursion(nums, mid + 1, r);

	return node;
}

console.log(sortedArrayToBST([-10, -3, 0, 5, 9])); // 数据一定是升序的数组

// @lc code=end