手撸二叉树之验证二叉搜索树
发布于: 4 小时前
Hello, 大家好，今天是我参加 9 月更文的第 9 天，今天给大家带来的关于二叉树相关的算法题是二叉树的左叶子之和，正文如下：
题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
示例 2：
解题思路
我们知道二叉搜索树的特性就是，中序遍历后得到的是一个有序的数组，所以我们可以通过在中序遍历的时候检查当前节点的值是否大于前一个中序遍历的值，如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是。
代码实现
复制代码
最后
复杂度分析：
时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
空间复杂度 : O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/e1a36ead46b85e2d38e9f3620】。文章转载请联系作者。
佛系编码 2019.05.13 加入
红鲤鱼与绿鲤鱼与驴。
评论