#3504. 判定完全二叉树
判定完全二叉树
题目描述:判断完全二叉树
给定一棵包含 个结点的有根二叉树,结点依次以 编号,根结点编号为 。
对于结点 ,其左儿子的编号记为 ,右儿子编号记为 。特别地,如果左儿子不存在则 ,如果右儿子不存在则 。
请你判断这棵二叉树是否为完全二叉树。
完全二叉树的定义: 一棵深度为 的二叉树,除了最后一层外,其余各层的结点数都达到最大值,并且最后一层的结点都靠左排列。换句话说,若设二叉树的深度为 ,则前 层都是满的,第 层的所有结点都集中在最左边。
输入格式
第一行,一个正整数 ,表示有根二叉树结点数量。
接下来 行,每行两个正整数 ,表示结点 的左儿子编号和右儿子编号。
输出格式
输出一行:
- 如果是完全二叉树,输出
yes - 如果不是完全二叉树,输出
no
数据范围
输入输出样例 #1
输入 #1
4
2 3
4 0
0 0
0 0
输出 #1
yes
样例解释 #1
对应的二叉树:
1
/ \
2 3
/
4
这是一棵完全二叉树
输入输出样例 #2
输入 #2
4
2 3
0 0
4 0
0 0
输出 #2
no
样例解释 #2
对应的二叉树:
1
/ \
2 3
/
4
结点 有左孩子 但没有右孩子,但结点 是叶子节点,导致最后一层结点 没有靠左排列(在结点 的右孩子位置出现了空缺)
输入输出样例 #3
输入 #3
3
2 3
0 0
0 0
输出 #3
yes
样例解释 #3
对应的二叉树:
1
/ \
2 3
这是一棵满二叉树,也属于完全二叉树