leetcode 二叉树的最大深度

104. 二叉树的最大深度

已解答

简单

方法一：后序遍历（DFS）

思路

使用递归方法计算二叉树的最大深度。
二叉树的最大深度可以表示为：
- 如果节点为空（即 root == None），那么深度为 0。
- 否则，树的最大深度为左子树和右子树的最大深度加 1。
递归地计算左右子树的深度，并返回它们的最大值加 1。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null ){
            return 0;
        }else{
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
    }
}

思路与算法

如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为

max(l,r)+1

复杂度分析

时间复杂度：O(N)，其中 N 是二叉树中的节点数。因为我们每个节点都需要访问一次。
空间复杂度：O(H)，其中 H 是二叉树的高度。在最坏情况下（树完全倾斜），递归栈的深度可能会达到树的高度。

示例

对于输入 root = [3,9,20,null,null,15,7]：

根节点 3 的左子树深度为 1，右子树深度为 2。
因此，最大深度为 2 + 1 = 3。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 如果节点为空，深度为 0
        if root is None:
            return 0
        # 递归求左右子树的深度
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        # 返回左右子树较大深度加 1
        return max(left_depth, right_depth) + 1

方法 2：迭代 DFS（使用栈）

可以用栈来实现 DFS，从根节点开始，将每个节点和对应的深度存入栈中，然后更新最大深度。

代码如下：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 特殊情况处理
        if root is None:
            return 0
        
        # 使用栈来进行 DFS，每个元素是 (节点, 深度)
        stack = [(root, 1)]
        max_depth = 0
        
        # 开始 DFS
        while stack:
            node, depth = stack.pop()
            if node:
                # 更新最大深度
                max_depth = max(max_depth, depth)
                # 将左右子节点及其深度加入栈
                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))
        
        return max_depth

方法二：层序遍历（BFS）

树的层序遍历 / 广度优先搜索往往利用队列实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

在计算二叉树的最大深度时，我们也可以使用广度优先搜索（BFS）来实现。BFS 会按层遍历二叉树，因此每遍历完一层，深度就增加 1。使用 BFS 的优点是，它逐层访问节点，可以在找到最远叶子节点时直接得出最大深度。

从根节点开始，将其加入队列，并初始化深度为 0。
每一层的节点都会被处理，并在遍历该层的所有节点后，深度增加 1。
当队列为空时，说明所有层都遍历完了，此时的深度就是树的最大深度。

代码实现

以下是 BFS 的实现代码，使用 Python 的 collections.deque 来实现队列操作：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 如果根节点为空，直接返回深度 0
        if root is None:
            return 0
        
        # 初始化队列并将根节点加入队列
        queue = deque([root])
        depth = 0
        
        # 开始 BFS
        while queue:
            # 每一层的节点数量
            level_size = len(queue)
            # 处理当前层的所有节点
            for _ in range(level_size):
                node = queue.popleft()
                # 将子节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # 当前层处理完，深度加 1
            depth += 1
        
        return depth