【LeetCode】104. 二叉树的最大深度【简单】

1. 题目描述

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

2. 解题思路 & 代码

2.1 递归：DFS（深度优先搜索）

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        
        return max(left_height, right_height) + 1

复杂度分析

1. 时间复杂度：我们每个结点只访问一次，因此时间复杂度为 $O(N)$，
   其中 $N$ 是结点的数量。
2. 空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用 $N$ 次（树的高度），因此保持调用栈的存储将是 $O(N)$。但在最好的情况下（树是完全平衡的），树的高度将是 $log(N)$。因此，在这种情况下的空间复杂度将是 $O(log(N))$。

2.2 迭代：DFS 深度优先

使用栈，将上述递归问题转化为迭代
使用栈，用 pop，即队尾出列

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = []
        stack.append([1, root])  # 从包含根结点且相应深度为 1 的栈开始
        depth = 0
        while stack:  # 栈不空
            current_depth, root = stack.pop()
            if root:
                depth = max(depth, current_depth)
                stack.append([current_depth + 1, root.left])
                stack.append([current_depth + 1, root.right])
        return depth

复杂度分析

1. 时间复杂度：$O(N)$。
2. 空间复杂度：$O(N)$。

2.3 BFS

使用队列，用 pop（0），即队头出列

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = []
        queue.append(root)
        depth = 0
        while queue:
            depth += 1
            for i in range(len(queue)):
                temp = queue.pop(0)
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
        return depth

参考：

1. LeetCode官方题解.