深度优先遍历问题

问题描述

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

解题思路

  1. 基本概念

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

  2. 递归思路

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

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

1
2
3
4
5
6
对于每个节点：
├── 如果节点为空
│   └── 返回 0
├── 递归计算左子树的深度
├── 递归计算右子树的深度
└── 返回 max(左子树深度, 右子树深度) + 1
  1. 示例分析
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
  1. 复杂度分析
    • 时间复杂度：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