Question

Java数据结构二叉树深度递归调用算法求内部算法过程详解

比如二叉树
1
2 3
4 5 6 7
这个二叉树的深度可见是2，
我是这么想的
根节点是1
f(1)=f(2)+1;
f(2)=f(4)+1;
f(4)=f(4的左)+1;
f(4的左)=0；
所以f(1)=3 先不说结果，我这样想的思路对吗？

我想知道递归那部分内部算法过程

int TreeDepth(CBTType treeNode){
int depleft,depright;
if(treeNode==null){
return 0;
}else{
depleft=TreeDepth(treeNode.left);
depright=TreeDepth(treeNode.right);
if(depleft>depright){
return depleft+1;
}else{
return depright+1;
}
}
}

Answer 1

二叉树
     1
  2    3
4  5 6  7
这个二叉树的深度是3，树的深度是最大结点所在的层，这里是3.

应该计算所有结点层数，选择最大的那个。

根据上面的二叉树代码，递归过程是：

f(1)=f(2)+1 > f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)计算类似上面，要计算左右结点，然后取大者

所以计算顺序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然后计算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 计算完毕，计算f(1.right) f(3) 跟计算f(2)的过程一样。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleft>depright){
    return depleft+1;
}else{
    return depright+1;
}

只有left大于right的时候采取left +1，相等是取right

追问

谢谢
那我一开始想的大致是对的罗？
为什么要用递归方法呢

追答

大致是对的。用递推代码比较简单吧，非递推需要借助其他数据结构来保存中间结果。