每日一练：LeeCode-98、验证二叉搜索树【二叉搜索树+DFS】

本文是力扣LeeCode-98、验证二叉搜索树【二叉搜索树+DFS】】学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

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

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

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

思路

验证⼆叉搜索树，就相当于变成了判断⼀个序列是不是递增的了

递归法

这道题最简单的思路：
由于是二叉搜索树，直接使用中序遍历树，并使用数组记录所有遍历节点的值，最后判断是否单调递增即可。

class Solution {
    List<Integer> list = new ArrayList<>();
    void traversal(TreeNode root){
        if(root==null)return;
        traversal(root.left);
        list.add(root.val);
        traversal(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        traversal(root);
        for(int i=1;i<list.size();i++){
            if(list.get(i)<=list.get(i-1))return false;
        }
        return true;
    }
}

我们把⼆叉树转变为数组来判断，是最直观的，但其实不⽤转变成数组，可以在递归遍历的过程中直接判断是否有序

需要明确的点：

我们要⽐较的是左⼦树所有节点⼩于中间节点，右⼦树所有节点⼤于中间节点。

1、确定递归函数，返回值以及参数
由于常规的递归遍历节点时，没有保存上一个遍历的节点，所有比较大小的时候，总会使用到Integer.MAX_VALUE之类的值作为比较的初始值，如果root.val不是Integer类型的，就会有很多适配性问题。所以此处递归使用保存上一个遍历的节点的方式。
中序遍历，验证遍历的元素是不是从⼩到⼤

		TreeNode pre = null;    // ⽤来记录前⼀个节点,用Integer最小值
		boolean isValidBST(TreeNode root)

2、确定终⽌条件
⼆叉搜索树也可以为空！

		if (root==null)return true;

3、确定单层递归的逻辑
中序遍历，验证遍历的元素是不是从⼩到⼤，想着遍历顺序就行，由于需要使用返回值，作判断，所以isValidBST需要返回值

		boolean left = isValidBST(root.left);
		// 中序遍历，验证遍历的元素是不是从⼩到⼤，想着遍历顺序就行
		if (pre!=null && pre.val>=root.val)return false;
		pre = root; // 记录前⼀个节点
		boolean right = isValidBST(root.right);
		return left&&right;

整体代码

class Solution {
    TreeNode pre = null;    // ⽤来记录前⼀个节点
    public boolean isValidBST(TreeNode root) {
        if (root==null)return true;
        boolean left = isValidBST(root.left);
        // 中序遍历，验证遍历的元素是不是从⼩到⼤，想着遍历顺序就行
        if (pre!=null && pre.val>=root.val)return false;
        pre = root; // 记录前⼀个节点
        boolean right = isValidBST(root.right);
        return left&&right;
    }
}