【专题二 二叉树中的深搜】98. 验证二叉搜索树
1.题目解析
2.讲解算法原理
二叉搜索树的中序遍历是一个有序序列
1.使用全局变量的优势
2.回溯
3.剪枝
- 左子树是二叉搜索树
- 当前节点符合二叉搜索树的定义
- 右子树是一个二叉搜索树
3.编写代码
/**
* 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 long prev=Long.MIN_VALUE;;
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
boolean leftnode=isValidBST(root.left);
boolean cur=false;
if(root.val>prev){
cur=true;
}
prev=root.val;
boolean rightnode=isValidBST(root.right);
return leftnode&&rightnode&&cur;
}
}