题目

给定一个二叉树，找出其最大深度。

难度：★★☆☆☆
类型：二叉树

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解答

方案1：递归法

递归法通过遍历所有结点寻找最大深度，时间复杂度为N。我们编写函数，确定以root为根结点的一棵树的最大深度这样：

1. 如果根结点root为空，则直接返回0；

2. 如果不为空，则是左子树的最大深度d1和右子树的最大深度d2中较大的值加1。

3. 左子树或右子树的最大深度可以通过调用本函数确定。

具体这样实现：

class Solution:
    """
    递归法
    """
    def maxDepth(self, root):
        def max_depth(root):                        # 计算以root为根节点的二叉树的最大深度
            if not root:
                return 0
            max_left = max_depth(root.left)         # 左子树最大深度
            max_right = max_depth(root.right)       # 右子树最大深度
            return max(max_left, max_right) + 1     # 加上根节点，返回当前子树最大深度
        return max_depth(root)

方案2：迭代法

我们把每一个结点及其对应的深度作为一条记录，使用栈这个数据结构来存储每条记录，遍历树的每一个结点，并用max_depth变量记录遍历到当前位置的最大深度，直到栈中为空为止。

class Solution:
    """
    迭代法
    """
    def maxDepth(self, root):
        stack = []                                              # 定义一个空栈，栈中的元素是结点及其对应的深度
        if root:                                                # 如果根结点不为空
            stack.append((root, 1))                             # 则将根节点及其对应深度1组成的元组入栈
        max_depth = 0                                           # 初始化最大深度为零
        while stack:                                            # 当栈非空时
            tree_node, cur_depth = stack.pop()                  # 弹出栈顶结点及其对应的深度
            if tree_node:                                       # 如果该结点不为空
                max_depth = max(max_depth, cur_depth)           # 更新当前最大深度，如果该结点深度更大的话
                stack.append((tree_node.left, cur_depth+1))     # 将该结点的左孩子结点及其对应深度压入栈中
                stack.append((tree_node.right, cur_depth+1))    # 将该结点的右孩子结点及其对应深度压入栈中
        return max_depth                                        # 返回遍历结束后的最大深度

如有疑问或建议，欢迎评论区留言~