二叉判定树是否是完全二叉树,b+树 二叉树 区别
BM35判断一棵完全二叉树是否描述了一棵给定的二叉树,判断它是否是一棵完全二叉树。
完全二叉树的定义:如果二叉树的深度为H,则除H层之外的所有层的节点数达到最大,H层的所有叶节点连续集中在最左侧,为完全二叉树。(H层可以包含[1~2h]个节点)
数据范围:符合的节点数
示例1:示例图2:示例图3:
示例1输入:
{1,2,3,4,5,6}
复制返回值:
真实的
复制
2示例输入:
{1,2,3,4,5,6,7}
复制返回值:
真实的
复制
3示例输入:
{1,2,3,4,5,#,6}
复制返回值:
错误的
如果解是完全二叉树,当第一个空节点出现时,后续所有节点只能是空节点;要么没有空节点,先遍历队列层次结构,然后向左再向右。
#包含位/标准数据。h
//https://www . now coder . com/practice/8d a4 dff 9 e 36409 ABBA 2 adbe 413 D6 FAE?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 complete tree(TreeNode * root)
{
if (root==nullptr)
{
返回true
}
if(root-left==nullptr root-right==nullptr)
{
返回true
}
STD:queue TreeNode * q;
q . push(root);
bool flag=false
而(!q.empty())
{
自动节点=q . front();
q . pop();
if (node==nullptr)
{
flag=true
}
其他
{
if(标志)
{
返回false
}
q.push(节点向左);
q.push(节点右移);
}
}
}
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。