‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者1.#includeiostream using namespace std; const int MAXN 1e6 5; int leftchild[MAXN]; int rightchild[MAXN]; int n; int getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth)1; } int main() { cin n; for (int i 1; i n; i) { cin leftchild[i] rightchild[i]; } int ans getdepth(1); cout ans; return 0; }用数组表示二叉树并求最大深度从原理到代码一篇讲透这道题是二叉树最基础、也是最重要的能力之一求二叉树的最大深度高度你这份代码写法很典型数组建树 递归DFS求深度。这篇文章我帮你把每一部分都讲清楚保证你不仅会写还知道为什么这么写。一、问题本质输入n节点个数 接下来 n 行 每个节点的 左孩子 和 右孩子例如5 2 3 4 5 0 0 0 0 0 0表示1 ├── 2 │ ├── 4 │ └── 5 └── 3二、数组建树核心思想int leftchild[MAXN]; int rightchild[MAXN];含义leftchild[i] → 节点 i 的左孩子 rightchild[i] → 节点 i 的右孩子关键点用“编号”代替指针特殊值0 表示没有子节点空节点三、什么是树的深度定义从根节点到最远叶子节点的路径长度举例1 / \ 2 3 / 4最大深度3四、核心函数解析DFSint getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth) 1; }这段代码在干什么一句话递归计算左右子树深度取最大值 1执行逻辑拆解递归终止条件if (node 0) return 0;空节点深度为 0递归计算左右子树int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]);返回当前节点深度return max(leftdepth, rightdepth) 1;当前节点 子树最大深度 自己这一层五、完整执行流程举例树1 ├── 2 │ ├── 4 │ └── 5 └── 3计算过程getdepth(1) → max(getdepth(2), getdepth(3)) 1 getdepth(2) → max(getdepth(4), getdepth(5)) 1 getdepth(4) → 1 getdepth(5) → 1 getdepth(2) → 2 getdepth(3) → 1 最终3六、主函数解析for (int i 1; i n; i) { cin leftchild[i] rightchild[i]; }含义节点编号就是 1 ~ n 默认根节点是 1求答案int ans getdepth(1);七、时间复杂度O(n)原因每个节点只访问一次八、空间复杂度O(n)来源递归栈数组存储九、常见错误1. 忘记处理 node 0会导致递归爆炸 / 访问非法2. 根节点写错getdepth(1); 前提是题目保证 1 是根3. 输入理解错误输入的是“编号”不是值十、进阶写法非递归 BFS如果不想用递归也可以用层序遍历// 用队列按层遍历统计层数适合防止递归爆栈十一、一句话总结树的深度 max(左子树深度, 右子树深度) 1