‹ 上一题 下一题 ›

g6-07534. 高度初值·叶子算 0 还是 1 未做

1000 ms 256 MB 测试点 ? 通过率 50% 自拟题知识点题GESP-66级·树形 DP 入门客观题单选

题目要求:每个点的「子树高度」定义为它到子树中最远叶子的边数(叶子高度 = 0)。

一位同学写了:

int dfs(int u) {
    int h = 1;                              // ← 初值写 1
    for (int v : ch[u]) h = max(h, dfs(v) + 1);
    return h;
}

树为 1-2、1-3、2-4(1 号是根)。这段程序对 1 号返回的值是( ),它与要求的定义差在哪?

  • A. 2;没有差别,叶子高度本来就是 1
  • B. 3;初值 h = 1 让叶子从 1 起算,整棵树的高度比定义多 1
  • C. 3;错在没有把 h 初始化成 0,与叶子无关
  • D. 4;错在把每个孩子的结果都加了 2
未选择
输入
输出

            
答案