给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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
1. 算法核心思想：明暗双线交织
这道题完美诠释了二叉树递归中的“双线任务”操作机制。 由于最长路径（直径）不一定经过整棵树的最顶端根节点，它可能藏在任意一个子树里，因此我们不能光靠函数的返回值来得到答案。
我们需要赋予每个节点两个职责：
- 明线任务（向上传递参数）：老老实实计算并向父节点汇报“以我为根的树，最大深度是多少”。
- 暗线任务（更新全局变量）：在汇报之前，偷偷把左手边的深度和右手边的深度加起来，算一算“如果以我作为这座桥的最高点，桥有多长？”一旦发现这座桥比历史记录
maxdeep还要长，立刻擦掉旧记录，写上新数字。
2. 代码逻辑拆解
-
为什么是后序遍历（左右根）？ 因为当前节点必须先等左孩子和右孩子把各自的深度汇报上来（
deepl(node->left)和deepl(node->right)），它自己才能进行加法运算。所以逻辑一定是“先左右，后自己”。 -
为什么深度汇报是
max + 1，而直径计算是直接相加？- 深度只能走一条路：要么偏左，要么偏右，所以是
max(左, 右)，再加上当前节点自己所在的这一层+1。 - 直径是一条横跨左右的“人”字形路线：左边走的距离加上右边走的距离，不需要再
+1，因为边的数量刚好等于左右节点深度的总和。
- 深度只能走一条路：要么偏左，要么偏右，所以是
class Solution {
public:
int maxdeep = 0;
int diameterOfBinaryTree(TreeNode* root) {
deepl(root);
return maxdeep;
}
int deepl(TreeNode* node) {
if (node == NULL) {
return 0;
}
int maxleft = deepl(node->left);
int maxright = deepl(node->right);
if (maxdeep < maxleft + maxright) {
maxdeep = maxleft + maxright;
}
return max(maxleft, maxright)+1;
}
};
3. 复杂度分析
- 时间复杂度：O(N)。其中 N 是二叉树的节点数。每个节点都会被访问且仅访问一次。
- 空间复杂度：O(H)。其中 H 是二叉树的高度。空间消耗主要来源于递归调用栈的深度，最坏情况下（树退化成链表）为 O(N)，最好情况下（平衡二叉树）为 O(logN)。