98. 验证二叉搜索树
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
实例2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
方法一：递归
递归有一个很重要的地方：我们在判断一个节点值大小关系的时候，要与它所有的祖先节点进对比，不能只跟父节点对比。所以我们可以定义一个 递归函数 reverseValidBST(TreeNode root, long minValue, long maxValue)。
函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
public boolean isValidBST(TreeNode root) {
return reverseValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean reverseValidBST(TreeNode root, long minValue, long maxValue) {
if (root == null) {
return true;
}
if (root.val <= minValue || root.val >= maxValue) {
return false;
}
return reverseValidBST(root.left, minValue, root.val) && reverseValidBST(root.right, root.val, maxValue);
}
方法二：中序遍历
根据二叉搜索树的性质我们可以得到：二叉搜索树的中序遍历是递增的。所以我们只需要中序遍历这棵树。判断结点的值是不是递增即可。
/**
* 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) {
if (root == null) {
return true;
}
Stack<TreeNode> queue = new Stack<>();
long lastNumber = Long.MIN_VALUE;
while (!queue.isEmpty() || root!=null) {
while (root!=null) {
queue.add(root);
root = root.left;
}
root = queue.pop();
if (root.val <= lastNumber) {
return false;
}
lastNumber = root.val;
root = root.right;
}
return true;
}
}