写点什么

算法攻关 - 验证二叉搜索树 (O(n))_098

发布于: 2021 年 03 月 11 日
算法攻关 - 验证二叉搜索树 (O(n))_098

一、题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树。


假设一个二叉搜索树具有如下特征:


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

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

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

示例 1:


输入:

   2

  / \

 1   3

输出: true

示例 2:


输入:

   5

  / \

 1   4

    / \

   3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

    根节点的值为 5 ,但是其右子节点值为 4 。


来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/validate-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路

一开始我的思路是 BFS 广度优先搜索。只要判断二叉搜索树的特性即可。然后忽略了一点是当利用了广度优先搜索,需要考虑局部解和全局解是否都是符合条件的。那么广度优先搜索只能保证局部左子树或者右子树符合,如果根节点的左右子树比较则无法权衡到。

那么第二种思路是,回归二叉树的三种遍历方式,先序遍历、中序遍历、后序遍历。我们采用中序遍历,则可以明确一点的是 局部解都是有序的,那么只要保证所有的左节点小于根节点即可

第三种思路是,利用递归的方式,也就是说左子树局部要满足二叉搜索树特性,并且还要满足整个二叉搜索树的特性 局部所有的左子树根节点小于 根 root。同理右子树。

三、代码实现

中序遍历

 public boolean isValidBST(TreeNode root) {  //创建一个栈  Deque<TreeNode> stack = new LinkedList<TreeNode>();      //这里int的处理边界范围        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;    }
复制代码

复杂度分析


时间复杂度 : O(n),其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)。


空间复杂度 : O(n),其中 n 为二叉树的节点个数。栈最多存储 n 个节点,因此需要额外的 O(n) 的空间

 public boolean isValidBST(TreeNode root) {            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);        }
public boolean isValidBST(TreeNode node, long lower, long upper) { if (node == null) { return true; } if (node.val <= lower || node.val >= upper) { return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); }
复制代码

复杂度分析


时间复杂度 : O(n)O(n),其中 nn 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)O(n)。


空间复杂度 : O(n)O(n),其中 nn 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 nn ,递归最深达到 nn 层,故最坏情况下空间复杂度为 O(n)O(n) 。

四、小结

递归的使用,各种数据结构的使用,需要灵活应用特性。


发布于: 2021 年 03 月 11 日阅读数: 8
用户头像

小胜靠智,大胜靠德 2019.06.27 加入

历经创业、京东、腾讯、滴滴公司,希望能够有些东西一起分享。公众号:小诚信驿站,微信/CSDN搜索:wolf_love666

评论

发布
暂无评论
算法攻关 - 验证二叉搜索树 (O(n))_098