验证二叉搜索树

2022 年 10 月 06 日
广西
本文字数：851 字
阅读完需：约 3 分钟

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1 和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源

第 7 天

验证二叉搜索树

难度：中等

题目

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

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

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

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

复制代码

题解

JavaScript 递归实现：

const helper = (root, lower, upper) => {    if (root === null) {        return true;    }    if (root.val <= lower || root.val >= upper) {        return false;    }    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);}var isValidBST = function(root) {    return helper(root, -Infinity, Infinity);};

复制代码

中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。

JavaScript 中序遍历实现：

var isValidBST = function(root) {    let stack = [];    let inorder = -Infinity;
    while (stack.length || 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;};

复制代码

总结

本题启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是。

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/8e475d7b6ebdbbd2c95b31565】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

真正的大师，永远怀着一颗学徒的心（易）

发布

暂无评论

创作场景

验证二叉搜索树

第 7 天

验证二叉搜索树

题目

题解

总结

掘金安东尼

评论