【近日力扣】验证二叉搜索树+将有序数组转换为二叉搜索树

• 总结：遇到树的题，可以先思考用哪种遍历方法，感觉遍历是常规解法

验证二叉搜索树（树，简单）

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

• 思路：很容易想到利用遍历，判断左子树值是否小于当前节点的，右子树值是否大于当前节点的，是的话继续分别遍历左右节点，直到不符合上述判断条件或者当前节点为 null（意味着遍历完成）

var isValidBST = function (root) {
	// 此处 low 和 up 的含义想通了就思路清晰了
	var erdogic = (root, low, up) => {
		if (root === null) return true
		if (root.val < low || root.val > up) return false
		// 对于左节点，第二个参数一直是 low，意味着递归只用来判断左子树值是否小于它的父节点值
		// 对于右节点，第三个参数一直是up，~判断右子树值是否大于它的父节点值
		return erdogic(root.left, low, root.val) || erdogic(root.right, root.val, up)
	}
	return erdogic(root, -Infinity, Infinity)
}

将有序数组转换为二叉搜索树（数组，简单）

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

• 思路：首先要定好根节点，由于是二叉搜索树，所以最好定升序数组的中位元素为根节点，则其左边元素设为左子树，右边元素同理，如此则遍历出一颗树。

var sortedArrayToBST = function (nums) {
	let erdogic = (left, right) => {
		if (left > right) return null
		let mid= Math.floor((left + right) / 2)
		let root = new TreeNode(nums[mid])
		root.left = erdogic(left, mid - 1)
		root.rigth = erdogic(mid + 1, right)
		return root
	}
	return erdogic(0, nums.length - 1)
}