【Hot 100 刷题计划】 LeetCode 543. 二叉树的直径 | C++ 后序遍历 (求深度的完美副产品)

LeetCode 543. 二叉树的直径

📌 题目描述

题目级别：简单

给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。
两节点之间路径的长度由它们之间边数表示。

• 示例 1:
  输入：root = [1,2,3,4,5]
  输出：3
  解释：3 ，取路径[4,2,1,3]或[5,2,1,3]的长度。

💡 破题思路：求深度的“副产品”

二叉树里任意一条路径，都可以看作是**“从某个节点往下走到左子树的最深处”，加上“从该节点往下走到右子树的最深处”**。
因此，穿过某个节点node的最长路径长度（边数）其实就等于：

左子树的最大深度 + 右子树的最大深度

这让我们立刻联想到了另一道极其经典的题：《104. 二叉树的最大深度》。
我们完全可以复用求最大深度的自底向上 (后序遍历)逻辑：

1. 递归求出左子树的深度L。
2. 递归求出右子树的深度R。
3. “夹带私货”：在拿到L和R的瞬间，穿过当前节点的直径也就知道了，就是L + R。我们用它去挑战并更新一个全局的max_diameter。
4. 回归主业：向父节点汇报当前子树的最大深度：max(L, R) + 1。

在求深度的过程中，顺手就把最大直径给求出来了，一鱼两吃！

💻 C++ 代码实现 (无副作用极简版)

classSolution{public:intdiameterOfBinaryTree(TreeNode*root){intmax_diameter=0;// 局部变量，避免多个测试用例导致的状态污染dfs(root,max_diameter);returnmax_diameter;}// 返回以 root 为根的子树的最大深度 (节点数)// 传入 max_diameter 的引用，实时更新最大直径intdfs(TreeNode*root,int&max_diameter){// 如果是空节点，深度为 0if(!root)return0;// 分别求左右子树的深度intL=dfs(root->left,max_diameter);intR=dfs(root->right,max_diameter);// 核心高光：穿过当前节点的路径边数，刚好就是左右子树的深度之和// 更新全局最大直径max_diameter=max(max_diameter,L+R);// 返回当前节点的最大深度给上一层returnmax(L,R)+1;}};