Maximum Depth of Binary Tree

104. 二叉树的最大深度

分析

初始化
- 创建一个变量 res，初始化为 0，用于记录树的最大深度
- 创建一个队列 q，用于辅助层序遍历
处理根节点
- 如果根节点 root 不为空，将其加入队列
层序遍历
- 每次从队列中取出当前层的所有节点（根据队列长度决定）
- 遍历当前层的节点，依次将每个节点的左右子节点加入队列
- 每处理完一层后，将深度变量 res 增加 1
返回结果
- 当队列为空时，树的所有层已遍历完，返回变量 res，即为最大深度

时间复杂度

每个节点被访问一次，因此时间复杂度为 O(n)，其中 n 是节点总数

空间复杂度

队列的最大空间取决于某一层的最大节点数。在完全二叉树的情况下，最大节点数可能是 n/2，因此空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


// BFS
class Solution
{
public:
    int maxDepth(TreeNode* root)
    {
        int res = 0;  // 初始化深度为 0
        std::queue<TreeNode*> q;  // 辅助队列，用于层序遍历

        if (root)
            q.push(root);  // 如果根节点非空，加入队列

        while (!q.empty())  // 队列非空时，继续遍历
        {
            int len = q.size();  // 当前层的节点数量

            // 遍历当前层的所有节点
            while (len--)
            {
                TreeNode* node = q.front();  // 获取队首节点
                q.pop();  // 弹出队首节点

                // 将当前节点的左右子节点加入队列
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            ++res;  // 每完成一层，深度加 1
        }

        return res;  // 返回最大深度
    }
};

// DFS
class Solution
{
public:
    int maxDepth(TreeNode* root)
    {
      if (!root) return 0;
      return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};