有序数组转换为二叉搜索树，验证二叉搜索树

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

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

题解：

虽然平衡树 AVL 相关的代码很麻烦，但是显然这道题并不涉及到 AVL 的平衡旋转的部分，我们只需要将排序好的数组选择中间节点作为根节点，则所建立的数一定是AVL树

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums, 0, nums.length - 1);}// --- 选择中间节点为根节点，必定为平衡二叉树private TreeNode build(int[] nums, int start, int end) {if (start > end)return null;int mid = (start + end) / 2;TreeNode node = new TreeNode(nums[mid]);node.left = build(nums, start, mid - 1);node.right = build(nums, mid + 1, end);return node;}
}

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -2^31 <= Node.val <= 2^31 - 1

题解：

​ 验证二叉搜索树，思路并不难，但是有一些细节的点可能会卡到，比如我们只判断一个节点的左子树小于该节点，右子树大于该节点，如下面的代码一样

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return helper(root);}private boolean helper(TreeNode node) {if (node == null)return true;if (node.left != null && node.left.val >= node.val)return false;if (node.right != null && node.right.val <= node.val)return false;return helper(node.left) && helper(node.right);}
}

但是如果出现这种的树，上面的代码就会判断为 true，这显然是错误的

​ 所以呢，我们需要给递归过程一个上界和下界来防止上述情况的发生，这里由于题干的数据取值范围是-2^31 <= Node.val <= 2^31 - 1，由于是闭区间，所以如果使用 Integer.MAX_VALUE 或者 Integer.MIN_VALUE 作为初始化的上下界的话，会出现边界值点判负的情况，所以这里应该取 Long.MAX_VALUE, Long.MIN_VALUE

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return helper(root, Long.MAX_VALUE, Long.MIN_VALUE);}private boolean helper(TreeNode node, long upper, long lower) {if (node == null)return true;if (node.val >= upper || node.val <= lower)return false;return helper(node.left, node.val, lower) && helper(node.right, upper, node.val);}
}

​ 当然了，除了递归判断之外，我们还可以中序遍历判断是否有序，这里我们没必要专门建立一个数组来存中序遍历的结果，没必要的空间复杂度吗，只要记录前一个访问节点的值并且更新即可，下面是两种中序遍历的解法，对于递归方式的中序遍历，由于Java的值传递机制，所以我们需要额外定义一个实例变量来记录，迭代的方法则不需要考虑这一点

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {long pre;public boolean isValidBST(TreeNode root) {pre = Long.MIN_VALUE;return helper(root);}// --- 中序遍历验证大小private boolean helper(TreeNode node) {if (node == null)return true;boolean flag = true;boolean l = helper(node.left);if (node.val <= pre) {return false;}pre = node.val;boolean r = helper(node.right);return flag && l && r;}
}

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<TreeNode>();long inorder = Long.MIN_VALUE;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();if (root.val <= inorder) {return false;}inorder = root.val;root = root.right;}return true;}
}