算法题（九）--二叉树的最大深度

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

一、题目

解法一：迭代法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #寻找最深的左节点
        def inner_find_left(root,stack_temp):
            while root != None:
                stack_temp.append(root)
                root = root.left
            return stack_temp
        stack = []
        stack = inner_find_left(root,stack)
        max_depth = 0
        pre_node =None
        while stack:
            #2、判断栈中最后一个节点的右节点是否为空，如果不为空则继续向下寻找
            temp = stack[-1]
            max_depth = max(max_depth,len(stack))
            if temp.right != None and temp.right != pre_node:
                stack = inner_find_left(temp.right,stack)
                continue
            #3、如果最后一德节点的右子节点为空，代表不用继续往下寻找，应该弹出栈里的元素
            pre_node = stack.pop(-1)
        return max_depth

解法二、递归法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.depth(root,0)
    def depth(self,root,n):
        if root == None:
            return n
        n += 1
        return max(self.depth(root.left,n),self.depth(root.right,n))

这篇关于算法题（九）--二叉树的最大深度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！