判断二叉树是否为二叉搜索树,二叉判定树和二叉搜索树
BM34确定它是否是二叉查找树。
知识点树
描述二叉树的根节点。请判断这棵树是不是二叉查找树。
二叉查找树满足每个节点的左子树上的所有节点都严格小于当前节点，并且右子树上的所有节点都严格大于当前节点。
示例：图1
图2
数据范围：满足节点数，满足节点上的值。
示例1输入：
{1，2，3}复制返回值：
虚假复印说明：
如图1的示例2所示，输入：
{2，1，3}复制返回值：
真实副本描述：
如图2所示，二叉查找树是一棵特殊的二叉树，其节点值大于其左子树，大于所有左子树，小于其右子树，小于所有右子树。因此，二叉查找树在某种程度上是一种排序结构。
递归实现-1对于搜索二叉树中的任意一个节点，其整个左子树的所有节点都小于当前节点的值，其右子树的所有节点都大于当前节点的值。实现步骤如下：
1.如果根节点为空，则返回true2。2.为根节点设置左右边界作为初始条件。3.判断当前节点及其左右边界。如果当前节点的值不在此区间内，则返回false4。4.递归判断当前节点的左右子树，同时更新左右边界。对于左侧节点，其右边界需要更新为父节点的值；对于右边的子树，它的左边界需要更新为父节点的值。
代码实现如下：
#包含位/标准数据。h
//https://www . now coder . com/practice/a 69242 b 39 BAF 45 de a 217815 c 7 dedb 52b？tpId=295 tags=title=难度=0判断状态=0 rp=0来源URL=/考试/oj
定义树结构
{
int val
struct TreeNode * left
struct TreeNode * right
TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}
};
bool is_valid_bst(TreeNode *root，int left，int right)
{
if (root==nullptr)
{
返回true
}
if(左=根值)
{
返回false
}
if(右=根值)
{
返回false
}
return is_valid_bst(root- left，left，root- val)is _ valid _ BST(root-right，root-val，right)；
}
bool isValidBST(TreeNode *root)
{
返回is_valid_bst(root，INT_MIN，INT _ MAX)；
}
递归实现-2第二茬搜索树的中序遍历是一个有序序列。如果我们按照中间顺序遍历给定的二叉树，记录当前节点的前任节点，然后在访问当前节点时与前任节点比较大小，实现如下：
long pre=INT _ MIN
//中间顺序遍历
bool isValidBST(TreeNode *root)
{
if (root==NULL)
返回true
//首先进入左边的子树
如果(！isValidBST(根-左))
返回false
if (root- val=pre)
返回false
//更新最大值
pre=root-val；
//再次输入右边的子树
如果(！isValidBST(根-右))
返回false
返回true
}
非递归实现非递归实现实际上可以通过中序遍历的非递归版本来实现。简要分析。
注：实际上可以通过保存一个前驱节点来判断是否严格有序，从而省略中间数组。
代码如下：
bool isValidBST(TreeNode *root)
{
//为遍历设置堆栈
堆栈TreeNode * s；
TreeNode * head=root
向量int排序；//按顺序记录遍历的数组。
而(头！=NULL ！s.empty()
{
//直到没有左节点
而(头！=空)
{
s.push(头)；
头=头-左；
}
head=s . top()；
s . pop()；
//访问节点
sort . push _ back(head-val)；
head=head-right；
}
//遍历中间顺序的结果
for(int I=1；I sort . size()；我)
{
//一旦有降序，就不是搜索树了
if(排序[i - 1]排序[i])
返回false
}
返回true
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。