原题链接🔗：二叉树的最大深度
难度：简单⭐️
题目
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
- 树中节点的数量在 [0, 104] 区间内。
- -100 <= Node.val <= 100
二叉树
二叉树的最大深度问题通常可以通过递归或迭代（使用队列）的方式来解决。
递归方法
递归方法是解决二叉树最大深度问题最直观的方式。其基本思想是：
- 如果当前节点为空，返回0。
- 否则，递归计算当前节点的左子树和右子树的最大深度。
- 返回左子树和右子树深度的最大值加1。
递归方法的C++实现如下：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return std::max(leftDepth, rightDepth) + 1;
}
};
迭代方法（使用队列）
迭代方法使用队列来实现广度优先搜索（BFS），其基本思想是：
- 初始化一个队列，将根节点入队。
- 当队列不为空时，进行循环：
- 记录当前层的节点数。
- 对于每一层的每个节点，访问其左右子节点（如果有的话），并将它们入队。
- 每完成一层的遍历，深度加1。
迭代方法的C++实现如下：
#include <queue>
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
std::queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int levelSize = q.size(); // 当前层的节点数
for (int i = 0; i < levelSize; ++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;
}
};
递归方法简单直观，但可能会遇到递归深度限制的问题，特别是在树非常高的情况下。迭代方法避免了递归深度限制的问题，但需要额外的空间来存储队列。在实际应用中，可以根据具体情况选择适合的方法。
题解
递归法
- 解题思路：
解决LeetCode上的"二叉树的最大深度"问题，主要涉及到树的深度优先搜索（DFS）策略。以下是解题的步骤和思路：
理解问题：首先明确题目要求，即找出二叉树的深度，也就是从根节点到最远叶子节点的最长路径上的边数。
递归策略：由于二叉树的最大深度问题天然适合用递归解决，可以定义一个递归函数maxDepth，该函数接收一个二叉树的节点作为参数。
递归终止条件：递归的基本终止条件是当节点为空时，此时树的深度为0。
递归逻辑：对于非空节点，需要分别计算其左子树和右子树的最大深度。
计算深度：对于每个非空节点，其深度等于其左子树深度和右子树深度中的较大者加1。
返回结果：递归函数最终返回的是根节点的深度。
编写递归函数：实现递归函数，使用条件语句来处理递归终止条件，并使用递归调用来计算左右子树的深度。
测试：编写测试用例来验证算法的正确性，包括但不限于只有一个节点的树、满二叉树、完全二叉树、不平衡二叉树等。
优化：考虑算法的时间复杂度和空间复杂度，确保递归的深度不会过大导致栈溢出。
- 复杂度：时间复杂度O(n)，n是二叉树的节点数；空间复杂度O(h)，h是二叉树高度。
- c++ demo：
#include <algorithm> // 用于std::max函数
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0; // 如果当前节点为空，返回深度0
}
// 计算左子树和右子树的最大深度
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
// 返回两个子树深度的最大值加1（当前节点的深度）
return std::max(leftDepth, rightDepth) + 1;
}
};
int main() {
Solution solution;
// 构建一个示例二叉树
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// 计算并打印二叉树的最大深度
std::cout << "The maximum depth of the binary tree is: " << solution.maxDepth(root) << std::endl;
// 清理内存
delete root->left;
delete root->right->left;
delete root->right->right;
delete root->right;
delete root;
return 0;
}
