day167—递归—二叉树的直径（LeetCode-543）
题目描述
给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。
两节点之间路径的长度由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]输出：3解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
解决方案：
这段代码是基于后序遍历（DFS）求解二叉树直径的经典实现，核心思路是通过递归计算每个节点的左右子树深度，同时统计以该节点为 “拐弯点” 的路径长度，最终得到整棵树的最大直径。
核心逻辑
核心定义：
ans：全局变量，记录二叉树的最大直径（即所有路径中的最长长度）；dfs(node)：递归函数，返回以node为根的子树的深度（从node到最远叶子节点的边数），同时在递归过程中更新全局最大直径。
递归边界：若
node为空（!node），返回 0（空树深度为 0）。后序遍历核心逻辑：
- 先递归计算左子树深度
l_len = dfs(node->left)； - 再递归计算右子树深度
r_len = dfs(node->right)； - 关键操作：以当前节点为 “拐弯点” 的路径长度是
l_len + r_len（左子树深度 + 右子树深度），用该值更新全局最大值ans； - 返回当前子树的深度：
max(l_len, r_len) + 1（取左右子树深度的最大值，加 1 表示当前节点到子树的一条边）。
- 先递归计算左子树深度
主函数逻辑：调用
dfs(root)触发递归遍历整棵树，最终返回全局最大值ans（即二叉树的直径）。
关键特点
- 时间复杂度 O (n)：每个节点仅被递归访问一次，n 为节点数；
- 空间复杂度 O (h)：h 为树的高度，递归栈深度等于树高（平衡树 h=logn，退化为链表 h=n）；
- 逻辑简洁：将 “计算子树深度” 和 “统计最大直径” 融合在一次 DFS 中，无需额外遍历；
- 直径定义：二叉树的直径是 “任意两个节点之间的最长路径长度”（路径长度 = 边数），该代码精准统计了所有可能的路径（以每个节点为拐弯点）。
验证示例（简单二叉树）
假设有如下二叉树：
plaintext
1 / \ 2 3 / \ 4 5- 递归到节点 2 时，
l_len=1（节点 4）、r_len=1（节点 5），ans更新为1+1=2； - 递归到节点 1 时，
l_len=2（节点 2 的子树深度）、r_len=1（节点 3 的子树深度），ans仍为 2（2+1=3？此处修正：该例子中节点 1 的l_len=2、r_len=1，ans会更新为 3，对应路径 4-2-5（长度 2）或 4-2-1-3（长度 3），最终直径为 3）； - 最终返回
ans=3，符合实际最长路径长度。
总结
- 核心思路：通过后序遍历递归计算子树深度，同时统计每个节点作为 “拐弯点” 的路径长度，取最大值即为二叉树直径；
- 关键设计：
dfs函数兼具 “返回子树深度” 和 “更新最大直径” 两个职责，是该问题的最优解法； - 功能效果：能正确计算任意二叉树的直径，时间 / 空间效率均为最优。
函数源码：
/** * 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; int dfs(TreeNode* node){ if(!node) return 0; int l_len=dfs(node->left); int r_len=dfs(node->right); ans=max(ans,l_len+r_len); return max(l_len,r_len)+1; } int diameterOfBinaryTree(TreeNode* root) { dfs(root); return ans; } };