题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

1. 问题理解

题目要我们计算二叉树的最大深度。

  • 最大深度：从根节点开始，一直走到最远的叶子节点，路径上节点的个数。

  • 根节点算第 1 层，每往下一层，深度加 1。

  • 叶子节点：左右子节点都为空的节点。

最长路径是 3 → 20 → 15 或 3 → 20 → 7，共有 3 个节点，所以最大深度是 3。

2. 核心算法 —— 递归（DFS 深度优先遍历）

思路：

  1. 如果节点为空（None），深度是 0（递归终止条件）。

  2. 递归计算左子树的深度 → leftheight

  3. 递归计算右子树的深度 → rightheight

  4. 当前节点的深度 = 1 + max(leftheight, rightheight)

    • 1 表示当前节点这一层

    • max(...) 取左右子树中更深的那一边

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.getdepth(root)
    def getdepth(self,node):
        if not node:
            return 0
        leftheight = self.getdepth(node.left)
        rightheight = self.getdepth(node.right)
        height = 1+ max(leftheight,rightheight)
        return height

3. 关键点和边界条件

  • 递归终止条件：节点为空时，返回 0（防止继续访问空节点）。

  • 叶子节点：左右都为空时，返回 1（当前节点本身就是一层）。

  • 只有左子树或只有右子树的情况：递归会自然处理，因为空的那一边返回 0。

  • 空树：输入 root = None，返回 0。

  • 时间复杂度：O(n)，每个节点只访问一次。

  • 空间复杂度：O(h)，h 是树的高度（递归栈的深度）。