PP4867 计算二叉树的高度（入门）

解题思路

第一步，理解题意。 题目给出一棵有 n 个结点的二叉树，1 号结点是根。每个结点一行，先给一个字母（结点的值），再给左孩子编号和右孩子编号，0 表示没有这个孩子。要求这棵树的高度。

第二步，先搞清楚"高度"怎么算。 从根出发，走到最深的叶子，路径上经过的结点个数就是树的高度。换个角度看：叶子结点的高度是 1，一个结点的高度等于它左右子树高度的较大值再加 1。没有左孩子就当作左子树高度是 0，没有右孩子就当作右子树高度是 0。

第三步，用递归。 写函数 hgt(x) 表示 x 号结点的高度：如果 x 是 0，说明是空结点，返回 0；否则分别求左孩子、右孩子的高度，取大的那个再加 1。从根 hgt(1) 开始调用，答案就出来了。

第四步，例子验证。 样例里根 1 往左走是 1→2→5→7，一路 4 个结点；往右走是 1→3→6，只有 3 个结点，所以高度取较大的 4，输出正是 4。

第五步，边界情况。 如果整棵树只有一个根结点（所有孩子都是 0），hgt(1) 里左右递归都返回 0，再加 1 得 1，正好是单结点树的高度，不会出错。

参考代码

// 计算二叉树的高度：叶子高度为 1，父结点高度等于较高子树加 1
#include <iostream>
using namespace std;

int lc[30], rc[30];  // 左、右孩子编号，0 表示没有孩子

int hgt(int x) {
    if (x == 0) return 0;
    int l = hgt(lc[x]);
    int r = hgt(rc[x]);
    return (l > r ? l : r) + 1;  // 取较高子树再加 1
}

int main() {
    int n, l, r;
    char c;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> c >> l >> r;  // c 是结点值，结点编号就是所在行号 i
        lc[i] = l;
        rc[i] = r;
    }
    cout << hgt(1) << endl;  // 根是 1 号结点
    return 0;
}

复杂度分析

每个结点在递归中只被访问一次，所以时间复杂度是 O(n)；空间主要是递归栈，最深是树的高度，也是 O(n)。n 最大只有 26，运行非常快。