二叉树节点深度

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)               #左子树寻找,子树每深入一层,depth1

        if level == 0:

           level = nodedepth(ptr.right,key,depth+1)          #右子树寻找

        return level

上一篇 下一篇

猜你喜欢

热点阅读