GESP 六级 · GESP202609 C++ 六级 第 8 题

下面函数用于计算二叉树的高度，横线处应填写（　　）。

int height(TreeNode *root) {
if (root == nullptr)
return 0;
int leftH = height(root->left);
int rightH = height(root->right);
return __________________________;
}

二叉树高度定义是根到最远叶子的路径节点数。递归时若根为空返回0，否则高度=左右子树高度最大值+1（当前节点本身）。这类题通法是：先写终止条件，再写子问题分解，最后用max取最长路径。

A把高度当总和，B取最小值算的是最短路径，C漏了+1只算子树高度。命题人利用"高度=子树高度"的直觉误区，以及"max"和"max+1"的边界差异。

1. 考纲定位

本题考查GESP六级《C++高级编程》中"递归算法"与"二叉树遍历"模块。命题人卡住的是学生"理解递归分解"与"高度定义"两个弱项——六级考生常把递归当循环用，或混淆高度与深度。

2. 解题思维

看到题先想：高度定义是什么？二叉树高度=根到最远叶子节点数。递归时，若根为空返回0（终止条件），否则高度由左右子树决定。关键观察：当前节点本身贡献1层，所以要在子树高度基础上+1。数值推演：假设左子树高3、右子树高2，则当前节点高max(3,2)+1=4。通法：递归树问题先写终止条件，再写子问题分解，最后用max取最长路径。