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

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

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

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

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

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

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

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

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

二、解题

1、思路分析

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

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

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

2、代码实现

代码参考：

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;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n为二叉树的节点个数，每个节点最多被访问一次。

空间复杂度： O(n)

其中n为二叉树的节点个数，栈最多存储n个节点。

三、总结

这道题根据搜索二叉树的属性：

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

递归调用所有节点，判断是否在合理的区间，在判断是否是合理的二叉搜索树。

递归的时候用了中序遍历，中序遍历是二叉树的一种遍历方式，先遍历左子树，再遍历根节点，最后遍历右子树。

二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。