#3504. 判定完全二叉树

判定完全二叉树

题目描述:判断完全二叉树

给定一棵包含 nn 个结点的有根二叉树,结点依次以 1,2,,n1,2,\dots,n 编号,根结点编号为 11

对于结点 ii,其左儿子的编号记为 lil_i,右儿子编号记为 rir_i。特别地,如果左儿子不存在则 li=0l_i=0,如果右儿子不存在则 ri=0r_i=0

请你判断这棵二叉树是否为完全二叉树

完全二叉树的定义: 一棵深度为 kk 的二叉树,除了最后一层外,其余各层的结点数都达到最大值,并且最后一层的结点都靠左排列。换句话说,若设二叉树的深度为 hh,则前 h1h-1 层都是满的,第 hh 层的所有结点都集中在最左边。

输入格式

第一行,一个正整数 nn,表示有根二叉树结点数量。

接下来 nn 行,每行两个正整数 li,ril_i, r_i,表示结点 ii 的左儿子编号和右儿子编号。

输出格式

输出一行:

  • 如果是完全二叉树,输出 yes
  • 如果不是完全二叉树,输出 no

数据范围

  • 1n1001 \leq n \leq 100

输入输出样例 #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

结点 33 有左孩子 44 但没有右孩子,但结点 22 是叶子节点,导致最后一层结点 44 没有靠左排列(在结点 22 的右孩子位置出现了空缺)

输入输出样例 #3

输入 #3

3
2 3
0 0
0 0

输出 #3

yes

样例解释 #3

对应的二叉树:

        1
       / \
      2   3

这是一棵满二叉树,也属于完全二叉树