题目描述

给定一个二叉树 root ，返回其最大深度。

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

示例

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

 提示

• 树中节点的数量在 [0, 10^4] 区间内。
• -100 <= Node.val <= 100

代码

 方法 1：递归（深度优先搜索，DFS）

class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;  // 空节点返回深度0int leftDepth = maxDepth(root->left);   // 计算左子树深度int rightDepth = maxDepth(root->right); // 计算右子树深度return 1 + max(leftDepth, rightDepth);  // 取较大值 + 1（当前节点）}
};

方法 2：层序遍历（广度优先搜索，BFS）

#include <queue>class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;queue<TreeNode*> q;q.push(root);int depth = 0;while (!q.empty()) {int size = q.size();  // 当前层的节点数for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();if (node->left) q.push(node->left);if (node->right) q.push(node->right);}depth++;  // 遍历完一层，深度加1}return depth;}
};