使用 C 递归算法求二叉树的深度

至于递归，你可以把它想象成一次运行一个句子。 当您需要保存状态时，系统会自动使用堆栈为您保存。 让我们以你说的例子为例：

n 是初始值为 0 的全局变量;

第一次调用 height（t），假设 t！ =null

由于 t！=null： 跳过 if （t==null） 返回 0;

关键是 u=height（t->lchild）; 调用自身的函数：此时，t->lchild 存储在堆栈中，由于是调用，因此必须从函数的开头开始执行：

看看这个时间 t2（实际上是 t->lchild），如果 （t==null） 返回 0;

假设 t 不为 null，当它遇到 u=height（t->lchild） 时，它将继续运行; 与功能本身保持一致-

假设它是 t->lchild==null。 好吧，这个函数执行返回 0;

慢：已计算第二个函数调用 u=height（t->lchild） 中的函数值。 在本例中，u=0;

您还记得第二个调用运行到 v=height（t->rchild）; 这句话，对吧？ 好的，所以这个过程与 u=height（t->lchild） 完全相同。

这里还假设得到的 v=0

第二个调用是 if （u>n） return （u+1）。

return (v+1)

要获得返回值，最好假设 u n，因此返回值为 1;

好了，这波浪潮结束了;

你还记得你第一次调用 height 时，它返回 u，u=1;

然后在第一次调用中执行到 v=height（t->rchild）; 完成。 同上。

这是一个复杂的过程。 让我们慢慢来。 呵呵。

int depth(btree root){int ldepth,rdepth;

if(!root)

return 0;

else{ldepth = depth(root-＞lchild);

rdepth = depth(root-＞rchild);

if（ldepth = rdepth） 通过在左右子树的最大深度上加 1 来返回。

return ldepth+1;

elsereturn rdepth+1;

return 1;只有根节点。