深度优先遍历问题

问题描述

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解题思路

  1. 基本概念

    • 二叉树的深度是从根节点到最远叶子节点的路径上的节点数
    • 叶子节点是指没有子节点的节点
    • 空节点的深度为 0

  2. 递归思路

    • 一个节点的最大深度 = max(左子树深度, 右子树深度) + 1
    • 递归的终止条件：当节点为空时，返回 0

  3. DFS（深度优先搜索）过程

    1
    2
    3
    4
    5
    6
    对于每个节点：
    ├── 如果节点为空
    │   └── 返回 0
    ├── 递归计算左子树的深度
    ├── 递归计算右子树的深度
    └── 返回 max(左子树深度, 右子树深度) + 1

  4. 示例分析

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    例如对于树：
        3
       / \
      9  20
         / \
        15  7

    计算过程：
    1. 节点3的深度 = max(节点9的深度, 节点20的深度) + 1
    2. 节点9的深度 = max(0, 0) + 1 = 1
    3. 节点20的深度 = max(节点15的深度, 节点7的深度) + 1
    4. 节点15和7的深度都是 1
    5. 所以节点20的深度是 2
    6. 最终树的深度 = max(1, 2) + 1 = 3

  5. 复杂度分析

    • 时间复杂度：O(n)，其中 n 是节点数量
    • 空间复杂度：O(h)，其中 h 是树的高度，最坏情况下为 O(n)

代码实现

1
2
3
4
5
6
7
class Solution:


    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1