以孩子兄弟链表为存储结构，请设计递归算法求树的深度。

[tag_link]

参考答案

对单棵树根调用：Depth(t)=0（t为空），否则 max(1+Depth(firstchild(t)), Depth(nextsibling(t)))；兄弟分支不增加层数。空森林深度0，单点树深度1（若采用边高则相应整体减1）。

推导过程

递归不变量：Depth(t) 是 t 所在兄弟链森林中，从该森林根到最深结点的层数。首孩子路径增加一层，兄弟路径仍在同层取最大，故归纳成立。每结点访问一次，时间 O(n)，栈 O(h_cs)，最坏 O(n)。

复杂度与边界

时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。

易错点

必须明确调用语义（单棵树根或森林链）和深度按层/按边的约定；不能让兄弟递归加1。

评分要点

• 写出核心结构对应关系或伪代码
• 给出正确性理由
• 给出复杂度与边界