牛客13279题解：利用递归与深度优先搜索计算树的最大高度（附完整代码）

一、题目解读

牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树（节点从0开始编号），需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n-1条边构成，保证为连通无环图。理解题目核心在于准确获取树的拓扑关系，并设计算法遍历各分支寻找最长路径。

二、解题思路

代码采用递归+深度优先搜索（DFS）策略。主函数通过邻接表构建树结构后，从根节点（索引0）出发递归计算：

1. 对每个子节点递归调用computeHeight()，获取其子树高度；

2. 取所有子树高度的最大值，并加1（当前节点自身高度）；

3. 最终返回根节点的高度即为整树最大高度。

此思路利用递归天然适配树结构的特点，简洁高效。

三、解题步骤

步骤1：输入处理与树构建

    读取节点数n，初始化邻接表tree（vector<vector>）；

    循环n-1次，输入父节点parent和子节点child，将child加入parent的邻接表列表。

步骤2：递归计算高度

    computeHeight()函数接收树和当前节点node：

    遍历node所有子节点，递归调用自身获取子树高度；

    用max()函数更新当前最高值，最终返回maxHeight+1。

步骤3：主函数输出结果

    调用computeHeight(tree, 0)计算根节点高度并输出。

四、代码和注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 递归计算以node为根的子树高度
int computeHeight(const vector<vector<int>>& tree, int node) {
    int maxHeight = 0;  // 初始化当前子树最大高度为0
    for (int child : tree[node]) {  // 遍历node的所有子节点
        maxHeight = max(maxHeight, computeHeight(tree, child));  // 递归计算子树高度并取最大值
    }
    return maxHeight + 1;  // 当前节点高度=子树最高高度+1
}

int main() {
    ios::sync_with_stdio(false);  // 加快输入/输出速度
    cin.tie(nullptr);            // 取消与cout的同步

    int n;
    cin >> n;                   // 输入节点数
    vector<vector<int>> tree(n);  // 邻接表存储树结构

    for (int i = 0; i < n - 1; ++i) {
        int parent, child;
        cin >> parent >> child;
        tree[parent].push_back(child);  // 构建父节点到子节点的边
    }

    cout << computeHeight(tree, 0) << endl;  // 计算根节点0的高度并输出
    return 0;
}

五、总结

本解法通过递归天然匹配树结构，避免了复杂的层次遍历或栈操作。时间复杂度为O(n)，空间复杂度为O(n)（递归栈深度）。适用于中小型树结构高度计算场景。需注意输入数据需严格保证为树，避免环导致递归无限循环。代码简洁性、可读性与效率平衡良好，是解决此类问题的经典范式。