首页 > 试题广场 >

判断一棵满二叉树是否为二叉搜索树

[编程题]判断一棵满二叉树是否为二叉搜索树
  • 热度指数：12570 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给定一棵满二叉树，判定该树是否为二叉搜索树，是的话打印True，不是的话打印False

说明：
a. 二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
b. 满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树
c. 树内节点数不超过 10000，非空节点值为大于0小于65536的整数，空树则输入None，空树我们也认为是二叉搜索树

数据范围：树上节点数满足 ，每个节点的值满足

输入描述:
从根节点开始，逐层输入每个节点的值，空树或空节点输入为None
比如：10,5,15,3,7,13,18


输出描述:
是二叉搜索树的话打印True，不是的话打印False
示例1

输入

10,5,15,3,7,13,18

输出

True
示例2

输入

None

输出

True
示例3

输入

10,5,15,3,4,13,18

输出

False

说明

节点值为 5 的左子节点和右子节点是 3 , 4 都小于根节点 5 ，所以不是二叉搜索树
算法知识视频讲解
开通博客
头像 白色高跟鞋
发表于 2020-04-29 01:36:44
讲真没必要那么麻烦真的去构建一棵树，直接利用二叉搜索树的性质，python十几行就结束了。 满二叉树： 深度为n时共2^n-1个节点 二叉搜索树： 左节点所有<=根节点<所有右节点 核心思路：中序遍历二叉搜索树应单调递增 (由题意知道节点最小值为0，因此预设pre为-1)；同时， 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 爱吃烤肠的小鲸鱼要暴富
发表于 2020-02-25 18:43:09
思路：从第二叉树的第二层开始判断，每两个节点一组，通过数组下标找到其父节点，根据规则对比 package NewCoder; import java.util.Scanner; public class IsBinarySearchTree { public static void ma 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 _Bingbong
发表于 2024-12-31 23:23:40
解题思路 这是一个判断满二叉树是否为二叉搜索树的问题。关键点： 二叉搜索树的性质： 左子树所有节点值小于根节点 右子树所有节点值大于根节点 左右子树也都是二叉搜索树 满二叉树的性质： 除最后一层外，每层节点都是满的 每个非叶节点都有两个子节点 数值范围： 节点值范围：(0, 6 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客445935160号
发表于 2021-08-28 01:42:48
result = 1 def search(a,i,x,y,z):     global result     if len(a) <= 1: 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Norewyx
发表于 2022-06-22 15:03:32
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) //主要思想，二叉搜索树应满足中序遍历（左中右）时，节点值单调递增 var pre,res=-1,true//pre为负数，所以第一轮无论根节点多小pre都会被 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 快手 运维工程师 前端工程师 算法工程师 树 测试工程师 PHP工程师 递归 2019 Java工程师
上传者：小小
难度：
64条回答 16246浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断一棵满二叉树是否为二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号