LeetCode|98. 验证二叉搜索树字符串|算法|数据结构|leetcod

98. 验证二叉搜索树给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：

文章图片

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

文章图片

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
思考根据这个二叉树的性质，中序遍历为有序序列。

文章图片

因为我们希望在递归执行过程中，我们希望有一个变量代表上一个访问节点的值。
所以这个变量应该是引用型变量。
这里我们先用栈简单尝试，效率好像不太高。

package 力扣; import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @author yyq * @create 2022-04-15 15:33 */ public class leetcode98 { public static void main(String[] args) { TreeNode root =new TreeNode(5); root.left=new TreeNode(4); root.right=new TreeNode(6); root.right.left=new TreeNode(3); root.right.right=new TreeNode(7); leetcode98 l=new leetcode98(); l.isValidBST(root); } public boolean isValidBST(TreeNode root) { if(root==null) return false; Stack stack=new Stack<>(); boolean flag = inOrder(root, stack); return flag; }private boolean inOrder(TreeNode root, Stack stack) { boolean flag = true; if(root.left!=null){ flag = inOrder(root.left,stack); if(flag==false) return false; }if(stack.isEmpty()) stack.push(root.val); else { Integer pop = stack.pop(); if(root.val<=pop) return false; stack.push(root.val); }if(root.right!=null){ flag = inOrder(root.right,stack); if(flag==false) return false; }return flag; }}

接下来我们可以使用数组来代替栈。
数组a[0]代表上一个数的值
【LeetCode|98. 验证二叉搜索树】数组start[0] 为-1代表没有对a[0]初始化
注意:a[0]的初始化值应该是树的左下角的叶子结点的值。

文章图片

public boolean isValidBST(TreeNode root) { if(root==null) return false; int[] a = new int[1]; int[] start = new int[1]; start[0] = -1; boolean flag = inOrder(root, a,start); return flag; }private boolean inOrder(TreeNode root, int[] a,int[] start) { boolean flag = true; if(root.left!=null){ flag = inOrder(root.left,a,start); if(flag==false) return false; }if(start[0]==-1) { a[0] = root.val; start[0] = 1; } else {if(root.val<=a[0]) return false; a[0] = root.val; }if(root.right!=null){ flag = inOrder(root.right,a,start); if(flag==false) return false; }return flag; }