java数据结构二叉树相关问题

Question

有点看不太懂递归.....代码如下，是求key值所在的层次
public int level(BinaryNode p,T key)
{
int level,level1,level2;
if(p==null)
level=0;
else if(p.data==key)
level=1;
else
{
level1=level(p.left,key);
level2=level(p.right,key);

if(level1==0&&level2==0)
level=0;
else
level=((level1>level2)?level1:level2)+1;
}
return level;
不懂为什么在递归的过程中会有值？？？就是那个level1和level2的值是怎么出来的？？咋比大小的
......真的不懂，求大神指导......

Answer 1

首先分成三块:
if ...{ level = 0 }
else if ...{ level = 1 }
else { level = 0 or level = 子树层数+1 }
return level

在else块 中的递归，你可以想象为一次普通的函数调用，此函数会返回一个int，代表从发现key往回走了多少步。

从逻辑看，假设有且仅有一个节点的值等于key的话，它会先走到那个节点返回1，这样调用它的那个函数，就会返回2，再上一层返回3，直到最初
调用此函数的地方（根节点）每一层都会加1，也就是key的层数返还给调用者。

level1 level2代表一个节点左树和右树发现key后返回到该节点的层数，如果左右都没发现key，返回0.