2 yanapupa yanapupa 于 2016.04.20 15:47 提问

中序遍历递增可以判断一棵树是BST树吗

看到有这种算法,但是还看见有人这是错误的,因为不是BST也会有中序遍历递增的情况,我只想到必须要是前提需要是二叉树,不知道谁能举个例子吗?

3个回答

litpud
litpud   2016.04.21 09:54

中序遍历严格递增即可判定就是BST树

yanapupa
yanapupa 灰常感谢QWQ
大约 2 年之前 回复
CSDNXIAOD
CSDNXIAOD   2016.04.20 15:52

判断一棵树是否BST
判断树是否是另外一棵树的子树
判断一棵树是否是BST
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

yanapupa
yanapupa 想打你:)
大约 2 年之前 回复
litpud
litpud   2016.04.21 09:47
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
判断一棵树是否是BST
很多面试都会问到这样一个问题: 给定一个二叉树,判断它是否是二叉查询树。 思路: 要判断是否是二叉查询树,标准就是看每一个节点是否满足:1、左节点及以下节点的值比它小;2、右节点及以下节点的值比它大。当然,前提是子节点都存在的情况。所以,我们需要从根节点不断向下递归,只要所有节点都满足,那么就是BST,否则,就不是。 代码: private boolean i
[LintCode]95.验证二叉查找树(二叉排序树/二叉搜索树) 中序遍历
给定一个二叉树,判断它是否是合法的二叉查找树(BST) 一棵BST定义为: 节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。 样例 一个例子: 2 / \ 1 4 / \ 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}. 思路:观察二叉查找
C++版 - 剑指offer 面试题24:二叉搜索树BST的后序遍历序列(的判断) 题解
剑指offer 面试题24:二叉搜索树的后序遍历序列(的判断) 题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。 提交网址: http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=
判断一棵二叉树是否为二叉搜索树(BST)
这里先简单介绍一下二叉查找树的性质: 递归定义节点的左子树中任意节点值小于根节点的值,节点的右子树中任意节点值大于根节点,且当前节点左右子树都必须是二叉查找树,不允许存在重复节点。 假设:节点的数据结构:struct node { int value; node* left; node* right; };方法1(错误示范:自己踩的坑)首先BST是一个递归定义:这样我们首先
BST树(Binary Search Tree)二叉搜索树
BST树为典型的数据结构,广泛应用于数据群的管理上,如
先序遍历和后序遍历为什么不能唯一地确定一棵树?
以前大学学数据结果的时候,我们就知道,根据一棵树的先序遍历和中序遍历,或者后序遍历和中序遍历序列,都可以唯一地确定一棵树。 树中的节点,分为度为0,1,2的结点。如果树中只有一个节点,那么可以唯一确定一棵树,即只有一个节点的树。 当树中结点个数大于等于2的情况,树中的叶子结点和它的父亲结点中,至少有一种存在如下的情况。(为方便起见,我们先从叶子节点入手)             
二叉查找树(5) - 判断一棵二叉树是否为BST
在本系列的第一篇文章中,已经介绍过了二叉查找树的一些性质: 节点的左子树中任意节点值小于根节点节点的右子树中任意节点值大于根节点左右子树都必须是二叉查找树,不允许存在重复节点。 基于上面的这些性质,自然的就得到了这种判断方式:树中的每个节点都有一个特定的值。 假设树的节点定义为: struct Node {         int key;         Node
【Java实现】判断一棵树是否为BST,一棵树是否为完全二叉树
给定一个二叉树,判断它是不是二叉搜索树。 思路:对于一棵二叉树,最简单的方法就是中序遍历,看是不是一个递增数列,如果是,则是一棵二叉搜索树,如果不是,则不是二叉搜索树。在这里用一个lastVisit去记录上一次搜索的节点。这个过程就是先找到最左下角的节点,更新lastVisit为这个节点的值,然后按照中序遍历依次更新即可。 代码: class Node { int data; Node
BST中序遍历(Iterative)
首先来看下 recursive 的版本: void inorder(TreeNode* node) { if (node != NULL) { inorder(node->left); //左子树 print(node->val); //当前节点 inorder(node->right); //右子树
BST树遍历O(n)时间复杂度+O(1)空间复杂度
问题描述BST树的遍历问题常常遇到,前序、中序、后序等。如果用递归的话,是非常方便的,其时间复杂度是O(n),空间复杂度是O(log n)级别。PS:stackoverflow问答网站上有一个问题指出,这类问题的复杂度不应该直接说是O(log n),因为编译器会进行一些优化,比如修改成尾递归等。不过我们这里暂时不考虑优化,从程序逻辑上来讲,BST递归遍历认为是O(log n)的复杂度。OK,那么如果