2186: 【基础】是否是完全二叉树

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

完全二叉树的特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部

现在根据边的连接情况判断一棵树是否是完全二叉树。

输入格式

第一行有2个整数n(0 < n < 1024)和r(1<=r<=n), 表示结点数和树根,接下来n-1行每行有2个整数a,b (1 <= a,b <= n)表示a结点和b结点有一条边相连,如果a是b的根结点,则b是a的左子结点,如果b是a的根结点,则a是b的右子结点(数据保证是一棵树而不是一座森林)

输出格式

如果是完全二叉树 输出yes 否则输出no

输入样例 复制

5 1
1 2
3 1
4 2
2 5 

输出样例 复制

yes

分类标签