LeetCode:98. 验证二叉搜索树

目录

题目描述:

代码:

第一种:

第二种:

第三种:

---

题目描述:

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

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

• 节点的左

  子树

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

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false

代码:

第一种:

范围递归

 public boolean isValidBST(TreeNode root) {return isValid(root,Long.MIN_VALUE,Long.MAX_VALUE);}private boolean isValid(TreeNode root, long minValue, long maxValue) {if(root==null){return true;}if(root.val<=minValue||root.val>=maxValue){return false;}return isValid(root.left,minValue,root.val)&&isValid(root.right,root.val,maxValue);}

第二种:

中序递归

 long pre=Long.MIN_VALUE;public boolean isValidBST2(TreeNode root) {if(root==null){return true;}boolean a=isValidBST2(root.left);//此时a已经为false,但还是会继续往下进行下去的if(!a){return false;}if(pre>=root.val){return false;}pre=root.val;return isValidBST2(root.right);}

第三种:

中序非递归

 public boolean isValidBST1(TreeNode root) {TreeNode p = root;LinkedList<TreeNode> stack = new LinkedList<>();long prev =Long.MIN_VALUE;while (p != null || !stack.isEmpty()) {if(p!=null){stack.push(p);p = p.left;}else{TreeNode pop= stack.pop();if(prev>=pop.val){return false;}prev = pop.val;p=pop.right;}}return true;}