☆打卡算法☆LeetCode 98、验证二叉搜索树算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

链接：98. 验证二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

二、解题

1、思路分析

这道题是验证根节点是否是二叉搜索树。

由题意可知，如果该二叉树左子树不为空，则左子树上所有节点的值都小于根节点的值，同样，右子树也一样。

那么，就可以使用一个递归函数，将根节点的最大值最小值以及当前节点的值传递进去，然后判断当前节点的值是否满足在根节点的最大值最小值区间内，不满足则直接返回，满足则继续递归检查。

2、代码实现

代码参考：

代码语言：javascript复制

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
              // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }
}