题目要求:每个点的「子树高度」定义为它到子树中最远叶子的边数(叶子高度 = 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