拿出来分享一下

 int pathLength(TARGETSET *set, int value) {

     if(set == NULL)  return 0;

     if(set->left == NULL && set->right == NULL)  return value ;

     return value + pathLength(set->left,value+1) + pathLength(set->right,value+1);

 }

调用的时候直接把value 设成0就好

[ 本帖最后由 madfrogme 于 2012-6-18 23:41 编辑 ]

int pathLength(TARGETSET *set) {

     if(set == NULL)  return 0;

     int lLength, rLength;
     lLength = pathLength(set->left);
     rLength = pathLength(set->right);

     return 1 + (lLength>rLength ? lLength : rLength);
}

可能你修改后的代码不是求 所有内部节点加在一起的 path length了

而是求一个Binary tree 的最大深度了（root的深度为0的话， 应该把return 0 改成 -1吧）

求内部节点path length的主要目的也就应该是判断Binary tree的性能吧，即是：我们需要比较多少次来找到我们需要的key

因为这个问题和key的internal path length 有直接关系，问题也可就可以转换为n 个key的binary tree，它的平均internal path length为多少了

如果没说错应该约等于 2ln(2)lg(n)  即 1.39lg(n)吧

嗯，我的代码就是求树深度的。

root的深度为0为什么要把return 0 改成 -1？

aaaa

[ 本帖最后由 madfrogme 于 2012-6-19 19:20 编辑 ]

因为看所有的地方都会说root的深度为0

所以不改为-1的话，最后相当于把root 也加了一个1进去

所以结果也就大1了

我是这么觉得的，而且编译一下好像确实是这么回事

若果有截屏证明我错了的话，我也会再验证一遍的