98. 验证二叉搜索树
题目:
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
解题思路:
利用二叉搜索树的中序遍历是严格的升序序列,如果中序遍历过程中当前节点值小于等于上一个节点值,那么就说明不是严格递增的,自然也就不是二叉搜索树了。
注意preVal的初始值为long型的最小值,因为题目的节点值可以取到int型的最小值,如果第一个遍历的节点值刚好等于int型的最小值就会出现误判(和preVal的初始值相等了,导致返回false)。
/*** 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 {private boolean ans = true;private long preVal = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {inorder(root);return ans;}private void inorder(TreeNode root){if(root == null){return;}inorder(root.left);if(root.val <= preVal){ans = false;return;}preVal = root.val;inorder(root.right);}
}