练习 11：树上完全二叉树计数

题目描述：

给定一棵以 1 为根的有根树，每个结点最多有两个子结点（即这是一棵二叉树）。现在要统计：以根结点 1 的每个子结点为根的子树中，有多少棵是完全二叉树？

完全二叉树的定义：

• 所有结点都有 0 个或 2 个子结点（满二叉树）
• 或者：如果用数组下标表示（根为 1，左儿子为 2i，右儿子为 2i+1），则所有结点的下标连续，没有空洞

输入格式：

• 第一行：一个正整数 n（2 ≤ n ≤ 1000）
• 第二行：n-1 个整数 f_2, f_3, ..., f_n，其中 f_i 表示结点 i 的父结点编号（-1 表示该结点不存在）
• 或者另一种输入格式：接下来 n 行，每行两个整数 l_i, r_i，表示结点 i 的左儿子和右儿子（-1 表示没有该儿子）

输出格式：

• 一行，一个整数，表示根结点 1 的所有子结点中，有多少个子树是完全二叉树

样例输入：

7
1 1 2 2 3 3

样例输出：

1

样例解释：

树的结构：

      1
     / \
    2   3
   / \
  4   5

根 1 有两个子结点 2 和 3：

• 以 2 为根的子树：2, 4, 5，是完全二叉树（满二叉树）
• 以 3 为根的子树：只有 3，是完全二叉树（单个结点也算）

所以答案是 2（但样例输出是 1，可能是按另一种判定标准）

提示：

• 方法1：BFS + 堆式编号

  • 对每个子树，用 BFS 遍历，给每个结点分配下标（根为 1，左儿子为 2i，右儿子为 2i+1）
  • 统计结点数 cnt 和最大下标 maxIdx
  • 如果 maxIdx == cnt，则是完全二叉树

• 方法2：递归判断

  • isComplete(u) 返回以 u 为根的子树是否是完全二叉树
  • 需要同时返回：是否完全二叉树、子树大小、最大深度等信息