day141—递归—二叉树的最大深度（LeetCode-104）

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解决方案（一）：

这段代码的核心功能是计算二叉树的最大深度（即从根节点到最远叶子节点的路径上的节点总数），采用「递归 + 分治」的后序遍历思路实现，时间复杂度O(n)（n为二叉树节点数），空间复杂度O(h)（h为树的高度，递归栈开销），是该问题的经典最优解法。

核心逻辑

代码利用递归的 “分治思想”，将求整棵树的最大深度拆解为求左右子树的最大深度，再合并结果：

1. 边界条件：若根节点root为空（空树 / 空节点），直接返回深度0；
2. 递归拆解：分别递归计算左子树的最大深度left_depth和右子树的最大深度right_depth；
3. 合并结果：当前节点所在子树的深度 = 左右子树深度的最大值 + 1（加1是因为要包含当前节点本身），返回该值。

总结

1. 核心思路：分治递归，将整棵树的深度问题拆解为左右子树的子问题，遵循「后序遍历」逻辑（先算左右子树，再算当前节点）；
2. 关键公式：当前节点深度 = max(左子树深度, 右子树深度) + 1，空节点深度为0；
3. 效率特点：每个节点仅遍历一次，时间O(n)；递归栈空间取决于树的高度（平衡树为O(log n)，退化为链表时为O(n)）。

函数源码（一）：

/** * 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) { if(!root) return 0; int left_depth=maxDepth(root->left); int right_depth=maxDepth(root->right); return max(left_depth,right_depth)+1; } };

解决方案（二）：

这段代码的核心功能是计算二叉树的最大深度（根节点到最远叶子节点的节点总数），采用「递归 + 前序遍历（深度优先遍历）」的思路，通过全局变量记录遍历过程中达到的最大深度，时间复杂度O(n)（n为节点数），空间复杂度O(h)（h为树的高度，递归栈开销），是该问题的另一种经典解法。

核心逻辑

代码通过 “遍历每个节点并统计深度” 的方式，而非分治思想，核心是用全局变量追踪遍历过程中的最大深度：

1. 全局变量初始化：定义ans并初始化为 0，用于保存最终的最大深度；
2. 递归辅助函数遍历：定义f函数，参数为当前节点node和当前遍历深度depth：
   • 边界条件：若当前节点为空，直接返回（无节点可统计）；
   • 深度更新：当前节点非空时，深度+1（包含当前节点），并更新ans为 “当前深度” 和 “历史最大深度” 的较大值；
   • 递归遍历：依次递归遍历当前节点的左子树和右子树，传递更新后的深度值；
3. 主函数触发遍历：调用辅助函数f(root, 0)（初始深度为 0，未访问任何节点），最终返回ans即为二叉树的最大深度。

总结

1. 核心思路：前序遍历（先处理当前节点，再遍历左右子树），遍历过程中逐节点统计深度，用全局变量记录最大值；
2. 解法特点：区别于 “后序分治（先算左右子树深度再合并）”，这是「遍历统计」思路，更直观体现 “深度遍历” 的过程；
3. 效率特点：每个节点仅遍历一次，时间O(n)，递归栈空间取决于树的高度，与分治解法效率完全一致。

函数源码（二）：

/** * 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 ans=0; void f(TreeNode* node, int depth){ if(!node) return; depth+=1; ans=max(depth,ans); f(node->left,depth); f(node->right,depth); } int maxDepth(TreeNode* root) { f(root,0); return ans; } };