Python教程

二叉树的最大深度-Python

本文主要是介绍二叉树的最大深度-Python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题:

# 给定一个二叉树,找出其最大深度。 
# 
#  二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 
# 
#  说明: 叶子节点是指没有子节点的节点。 

方法:迭代

 

def maxDepth(root):
    """ 在栈的帮助下将递归转换为迭代
    :param root:
    :return:
    """
    stack = []      # 申请栈空间,存储当前节点和对应的最大深度
    # 如果存在root,进行初始化工作
    if root is not None:
        stack.append((1, root))
    depth = 0
    while stack != []:
        current_depth, root = stack.pop()   # 弹出当前节点和对应的深度
        if root is not None:        # 如果存在下一节点
            depth = max(depth, current_depth)       # 更新深度
            # 同时要把当前更新depth信息同步到左孩子与右孩子
            stack.append((current_depth+1, root.left))
            stack.append((current_depth+1, root.right))
    return depth

 

这篇关于二叉树的最大深度-Python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!