二叉树节点深度
2019-11-22 本文已影响0人
mysimplebook
本质上使用深度优先遍历,如果深入到叶子节点没有找到,返回0,如果找到返回当前所在的层次。算法首先从左子树开始,如果左子树中没找到,就需要到右子树去寻找。
def nodedepth(ptr,key,depth=1): #假定根的深度为1
if ptr is None:
return 0
#print ptr.data
if ptr.data == key:
return depth #返回深度
level=nodedepth(ptr.left, key,depth+1) #左子树寻找,子树每深入一层,depth加1
if level == 0:
level = nodedepth(ptr.right,key,depth+1) #右子树寻找
return level