给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
1. 算法核心思想：深度优先搜索（DFS）
面对树形结构的“深度”问题，最直观的解法就是深度优先搜索（DFS）。
- 探险家身上带着一个计步器（
deep）。 - 每往下走一层（遇到一个真实的节点），计步器就加 1（
deep++）。 - 当走到没路了（
node == NULL），就把当前计步器上的数字记下来。 - 遇到分叉口时，分别去左边和右边探险，最后把两边记录的数字比一比，谁大就向上级汇报谁。
2. 代码逻辑拆解
- 状态传递（传值）： 注意这里的
deep是传值调用（没有加&）。这非常关键且正确！因为在树的分叉口，左子树和右子树应该是两条平行的探险路线，它们需要各自拥有一份当前深度的“复印件”，互不干扰。如果加了&，左右子树的深度就会互相污染。 - 分治与汇总：
SeekDeep函数完美体现了分治法（Divide and Conquer）。左子树和右子树分别去算自己的深度，最后通过if-else返回两者之间的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
int deep = 0;
return SeekDeep(deep, root);
}
int SeekDeep(int deep, TreeNode* node) {
if (node == NULL){return deep;}
deep++;
int rdeep = SeekDeep(deep, node->right);
int ldeep = SeekDeep(deep, node->left);
if (rdeep > ldeep) {
return rdeep;
}
else {
return ldeep;
}
}
};
3. 复杂度分析
- 时间复杂度：O**(N)**。其中 N 为二叉树的节点个数。因为无论是左子树还是右子树，树上的每一个节点都会被精确地访问一次。
- 空间复杂度：O**(H)**。其中 H 为树的高度。空间消耗主要来自于递归时系统调用的栈空间。在最坏情况下（树退化成一条直线），空间复杂度为 O(N)；在最好情况下（完全二叉树），空间复杂度为 O(logN)。