LeetCode算法题(Go语言实现)_33

题目

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

一、代码实现

func maxDepth(root *TreeNode) int {// 递归法（后序遍历）if root == nil {return 0}leftDepth := maxDepth(root.Left)rightDepth := maxDepth(root.Right)return max(leftDepth, rightDepth) + 1
}// 层序遍历法（BFS）
func maxDepthBFS(root *TreeNode) int {if root == nil {return 0}queue := []*TreeNode{root}depth := 0for len(queue) > 0 {levelSize := len(queue)for i := 0; i < levelSize; i++ {node := queue[0]queue = queue[1:]if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}depth++}return depth
}

二、算法分析

1. 核心思路

• 递归分治：将问题分解为左右子树的最大深度计算，最终合并结果
• 层序遍历：通过队列逐层扫描节点，统计层数即为最大深度
• 数学公式：maxDepth(root) = max(maxDepth(left), maxDepth(right)) + 1

2. 关键步骤

1. 递归终止条件：节点为nil时返回深度0
2. 递归分解：分别计算左右子树深度
3. 合并结果：取子树深度最大值加1
4. BFS队列处理：每次处理完一层节点后深度+1

3. 复杂度

方法	时间复杂度	空间复杂度	适用场景
递归法	O(n)	O(h)，h为树高度	树平衡时效率高
层序遍历法	O(n)	O(n)，最坏情况	避免递归栈溢出

---

三、图解示例

以二叉树[3,9,20,null,null,15,7]为例：

    3/ \9  20/  \15   7

递归过程：

1. 节点3深度 = max(节点9深度1，节点20深度2) +1 → 3
2. 节点20深度 = max(节点15深度1，节点7深度1) +1 → 2

层序遍历过程：

1. 第1层：3 → depth=1
2. 第2层：9,20 → depth=2
3. 第3层：15,7 → depth=3

四、边界条件与扩展

1. 特殊场景验证

• 空树：返回0
• 单节点树：返回1
• 左斜树：深度等于节点数（如链表结构）
• 满二叉树：深度为log₂(n+1)

2. 多语言实现

# Python递归实现
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root: return 0return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1# Python层序遍历
from collections import deque
def maxDepthBFS(root):if not root: return 0q = deque([root])depth = 0while q:depth += 1for _ in range(len(q)):node = q.popleft()if node.left: q.append(node.left)if node.right: q.append(node.right)return depth

// Java递归实现
class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}// Java层序遍历
class Solution {public int maxDepthBFS(TreeNode root) {if(root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while(!queue.isEmpty()){depth++;int size = queue.size();while(size-- > 0){TreeNode node = queue.poll();if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);}}return depth;}
}

五、总结与扩展

1. 核心创新点

• 分治思想：将复杂问题分解为可重复解决的子问题
• 空间优化：递归法空间复杂度仅与树高相关
• 遍历统一：层序遍历框架可扩展用于求平均值、右视图等问题

2. 扩展应用

• 最小深度：修改递归终止条件
• 平衡判断：结合深度计算判断子树高度差
• 序列化二叉树：结合层序遍历实现
• N叉树深度：递归时遍历所有子节点取最大值

3. 工程优化方向

• 尾递归优化：改造递归为尾递归形式避免栈溢出
• 迭代器模式：实现层次遍历迭代器减少内存消耗
• 并行计算：对左右子树深度计算进行多线程优化