返回信息流RT，在求二叉树的深度的时候，LZ写了如下的递归算法：
template <class T> int BiTree<T>::GetDepth(BiNode<T> *R)
{
int ldepth = 0, rdepth = 0;
if(R != NULL)
{
ldepth=1;
rdepth=1;
ldepth += GetDepth(R->lchild);
rdepth += GetDepth(R->rchild);
}
else
{
return ldepth>rdepth?ldepth:rdepth;
}
在对这样的一个二叉树求深度的时候，总是少1
R
I C
K Y X U
O M G
但是如果这样写的话，就能计算正确：
template <class T> int BiTree<T>::GetDepth(BiNode<T> *R)
{
if(R == NULL)
return 0;
int ldepth = 1, rdepth = 1;
ldepth += GetDepth(R->lchild);
rdepth += GetDepth(R->rchild);
return ldepth>rdepth?ldepth:rdepth;
}
我怎么觉得这两段代码是一样的呢？不知道哪儿考虑得出了问题，希望大神指点一下哪
这是一条镜像帖。来源：北邮人论坛 / cpp / #90490同步于 2016/3/8
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[问题]一个递归函数的问题
Pod
2016/3/8镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
不是，卤煮的问题大了
逻辑就不对啊
if(R != NULL)
{
int ldepth=1;
int rdepth=1;
ldepth += GetDepth(R->lchild);
rdepth += GetDepth(R->rchild);
return ldepth>rdepth?ldepth:rdepth;
}
else
{
return 0;
}
嗯~我一开始也是这样写的，无意中多想了一下问的那段代码，想不太明白，所以来请教一下大家
【 在 FromMars 的大作中提到: 】
: 不是，卤煮的问题大了
: 逻辑就不对啊
: if(R != NULL)
: ...................
看看
int 0, 0;
……
else
{ //两个都是0，还需要判断大小吗？
}
然而我也想不懂为啥卤煮代码顶层的那个节点不返回也没有报错……
ps 卤煮代码没有贴全？
【 在 Pod 的大作中提到: 】
: 嗯~我一开始也是这样写的，无意中多想了一下问的那段代码，想不太明白，所以来请教一下大家
果然是未定义行为
http://en.cppreference.com/w/cpp/language/return
If control reaches the end of a function without encountering a return statement, return; is executed (except in the main function, where return 0; is executed).
Flowing off the end of a value-returning function (except main) without a return statement is undefined behavior.
学到了啊，哈哈哈，有暖神风范[em68]
【 在 xiaobing307 的大作中提到: 】
: 果然是未定义行为
: http://en.cppreference.com/w/cpp/language/return
: If control reaches the end of a function without encountering a return statement, return; is executed (except in the main function, where return 0; is executed).
: ...................
【 在 xiaobing307 的大作中提到: 】
: ls应该是正解，但为啥不会报错呢？难道是未定义行为？ @nuanyangyang
嗯。如果if条件为真，会执行到函数末尾而遇不到return。这确实是未定义行为。
这个函数完全可以用“函数式”的风格写的。试试下面这种“变量初始化之后就再也不改变值”的写法：
template <class T> int BiTree<T>::GetDepth(BiNode<T> *R)
{
if(R != NULL)
{
int ldepth = GetDepth(R->lchild); // ldepth定义之后就再也没改变过
int rdepth = GetDepth(R->rchild); // rdepth定义之后就再也没改变过
int maxdepth = ldepth>rdepth?ldepth:rdepth; // maxdepth定义之后也再也没改变过
return maxdepth + 1; // 这个函数里任何变量的值都没改变过
}
else
{
return 0; // 所有的分支都有return
}
}
如果愿意的话，学学Haskell怎么样？