leetcode98. 验证二叉搜索树

leetcode 98.验证二叉搜索树
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree

题目描述

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

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

示例2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

递归法

解题思路

搜索二叉树是要满足左节点比头节点小，头节点比右节点小，
左子树上的最大值小于头节点，右子树的最小值，大于头节点、
在递归时，除了要判断左小于头，头小于右，
还有判断左边最大值和右边最小值分别和头节点比较，
因此我们要对递归遍历进行改造，加上最大值和最小值。

代码演示

public boolean isValidBST(TreeNode root) {//初始时 传的是 null ,nullreturn process1(root,null,null);}/*** min 最小值* max 最大值*/public boolean process1(TreeNode root,TreeNode min,TreeNode max){//base case if(root == null){return true;}//遍历右树时，任何值不能小于min 的值 ，否则返回false;if(min != null && root.val <= min.val){return false;}//遍历左树时，任何值不能大于max 的值 ，否则返回false;if(max != null && root.val >= max.val){return false;}//左树上的任何值 不能大于头节点的值，因此最大值传rootboolean isLeft = process1(root.left,min,root);//右树上的任何值 不能小于头节点的值，因此最小值传rootboolean isRight = process1(root.right,root,max);return isLeft && isRight;}

中序遍历解法

解题思路

中序遍历结果是：左头右。
搜索二叉树特性：左 < 头 < 右，
因此遍历出来的顺序是个递增的结构，
根绝这个特性来判断是不是搜搜二叉树

代码演示

List<TreeNode> ans = new ArrayList<>();public boolean isValidBST(TreeNode root) {process(root);for(int i = 1; i < ans.size();i++){if(ans.get(i).val <= ans.get(i-1).val){return false;}}return true;}/*** 中序遍历*/public void process(TreeNode root){if(root == null){return;}process(root.left);ans.add(root);process(root.right);}