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  先不说结果，我这样想的思路对吗？

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

...比如二叉树
   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;
}
  }
}展开

wzhappysnail · 2018-4-30 01:53:11

二叉树
聽聽聽聽 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

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

1 个回复