算法攻关 - 验证二叉搜索树 (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。同理右子树。
三、代码实现
中序遍历
复杂度分析
时间复杂度 : O(n),其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)。
空间复杂度 : O(n),其中 n 为二叉树的节点个数。栈最多存储 n 个节点,因此需要额外的 O(n) 的空间
复杂度分析
时间复杂度 : O(n)O(n),其中 nn 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次,因此时间复杂度为 O(n)O(n)。
空间复杂度 : O(n)O(n),其中 nn 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的高度。最坏情况下二叉树为一条链,树的高度为 nn ,递归最深达到 nn 层,故最坏情况下空间复杂度为 O(n)O(n) 。
四、小结
递归的使用,各种数据结构的使用,需要灵活应用特性。
版权声明: 本文为 InfoQ 作者【小诚信驿站】的原创文章。
原文链接:【http://xie.infoq.cn/article/d92a68e75f1a6ebd2e224719e】。文章转载请联系作者。
评论