一、问题描述

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

二、方案一：递归法

1、思路

递归是一种常用的解决树相关问题的方法。对于求二叉树的最大深度，我们可以这样思考：

• 如果二叉树为空，其深度为0。
• 如果二叉树不为空，二叉树的深度等于左子树和右子树的最大深度加1。

2、代码实现

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 计算左子树的最大深度
    leftDepth := maxDepth(root.Left)
    // 计算右子树的最大深度
    rightDepth := maxDepth(root.Right)
    // 返回左右子树的最大深度加1
    return max(leftDepth, rightDepth) + 1
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点只被访问一次。
• 空间复杂度：O(height)，其中 height 是二叉树的高度。空间复杂度主要取决于递归栈的深度，而递归栈的深度在最坏情况下等于二叉树的高度。

三、方案二：迭代法（层序遍历）

1、思路

层序遍历二叉树，使用队列来存储每一层的节点，每遍历一层，深度加1。

2、代码实现

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 初始化队列和深度
    queue := []*TreeNode{root}
    depth := 0
    for len(queue) > 0 {
        // 当前层的节点数
        size := len(queue)
        // 遍历当前层的所有节点
        for i := 0; i < size; 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)
            }
        }
        // 遍历完一层，深度加1
        depth++
    }
    return depth
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点只被访问一次。
• 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度主要取决于队列的存储空间，队列中的元素个数不会超过二叉树的节点数。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n)	O(height)	递归法
方案二	O(n)	O(n)	迭代法

递归法较为简洁，但需要考虑递归栈的深度。迭代法使用队列，空间复杂度较高，但不需要考虑递归栈的深度。根据具体需求选择合适的方案。