如何求二叉树的直径和最大路径和？

简化版

这两题是同一个套路——「后序递归 + 用全局变量记录经过某节点的最优解」。递归函数返回「从当前节点往下能延伸的最优单边值」（直径返回单边最大深度、路径和返回单边最大和），同时在每个节点处计算「左 + 当前 + 右」更新全局答案。区别只在于统计的是「边数/节点数」还是「节点值之和」。

详细版

二叉树的直径

直径 = 树中任意两节点间最长路径的边数（这条路径不一定过根）。经过某节点的最长路径 = 左子树最大深度 + 右子树最大深度。

int diameter = 0;
int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}
int depth(TreeNode node) {          // 返回：以 node 为根往下的最大深度（边数）
    if (node == null) return 0;
    int left  = depth(node.left);
    int right = depth(node.right);
    diameter = Math.max(diameter, left + right);  // 经过 node 的路径边数
    return Math.max(left, right) + 1;             // 往上只能选一条边延伸
}

二叉树的最大路径和

路径和 = 路径上节点值之和，路径可从任意节点到任意节点。经过某节点的最大路径和 = 该节点值 + 左侧最大贡献 + 右侧最大贡献（负贡献舍弃）。

int maxSum = Integer.MIN_VALUE;
int maxPathSum(TreeNode root) {
    gain(root);
    return maxSum;
}
int gain(TreeNode node) {           // 返回：从 node 往下单边能贡献的最大和
    if (node == null) return 0;
    int left  = Math.max(gain(node.left),  0);   // 负的就不要（取 0）
    int right = Math.max(gain(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);  // 经过 node 的路径和
    return node.val + Math.max(left, right);             // 往上只能带一条边
}

完整版教学

一、共同套路：树形 DP 的「拐点」思想

这两题都属于「树里找一条最优路径」。关键洞察是：任何一条路径，都有一个「最高点」（拐点）——路径在这个节点从左子树拐向右子树。 于是可以枚举每个节点作为拐点，计算「经过它、由左右两条向下的臂拼成」的路径值，取全局最大。

遍历用后序（先拿到左右子树的信息，再算当前节点）。
用一个全局变量记录「以每个节点为拐点」的最优解。
递归返回值只能是「单边」的贡献（左或右选一条），因为返回给父节点后，父节点要把它当成一条向下的臂，路径不能有分叉。

二、为什么返回值是「单边」，全局更新是「两边」

这是本类题最容易混的点：

更新全局答案时用 左 + 当前 + 右——因为以当前节点为拐点的路径可以同时用上左右两条臂。
返回给父节点时只能用 当前 + max(左, 右)——父节点要把当前子树当作「一条向下延伸的直线」，如果带了左右两条臂就分叉了，没法再往上接。

一句话：「算答案可以拐弯，往上传只能走直线」。

三、直径与路径和的差异

	直径	最大路径和
统计对象	边数（或节点数）	节点值之和
单边返回	`max(左,右) + 1`	`node.val + max(左,右)`
全局更新	`左 + 右`	`node.val + 左 + 右`
负值处理	不涉及	负贡献舍弃（和 0 取大）

最大路径和多了一步：如果某侧子树的贡献是负的，就不要它（取 0），因为负数只会拖累总和。直径不需要这步（深度总是非负）。

四、易错点

直径是边数：left + right 就是经过该节点的路径边数，不用再 +1（若题目要节点数则 +1）。
路径和的负值舍弃：Math.max(gain(child), 0)，漏了会在有负节点时算错。
全局变量初始值：路径和至少包含一个节点，maxSum 初值要设成最小值（不能设 0，否则全负节点的树会错）。
更新全局和返回值是两个不同的表达式，别写成一样。

五、这是一类题的模板

「二叉树中某种最优路径/最优子树」——直径、最大路径和、最长同值路径、打家劫舍 III 等，都是这个「后序递归 + 全局变量记录拐点最优 + 返回单边值」的模板。认出这个模式，一类题就都会了。

这节要真正讲透，需要把结论落到结构变化上：在如何求二叉树的直径和最大路径和？里，每一步操作都会影响某个指针、索引、节点关系或辅助状态。可以主动说明“操作前满足什么不变量、操作后这个不变量如何继续成立”，再补一个 3 个节点或 5 个元素的小例子。这样读者不仅知道答案，还能自己推导同类变体。

六、常见误区与追问

对比点	递归返回值	全局答案更新
二叉树直径	`max(leftDepth, rightDepth) + 1`	`leftDepth + rightDepth`
最大路径和	`node.val + max(leftGain, rightGain)`	`node.val + leftGain + rightGain`

记忆钩子：往上交差只能交一条链，自己结算答案时才可以把左右两条链拼起来。

误区：递归返回值可以同时包含左右两边。 返回给父节点后还要继续接到父节点，路径不能分叉，所以只能返回单边贡献。
误区：直径一定经过根节点。 最长路径可能完全在某个子树内部，因此要枚举每个节点作为拐点并维护全局最大值。
误区：最大路径和的全局变量可以初始化为 0。 如果整棵树节点值全为负数，答案应该是最大的那个负数，初始化为 0 会错。
误区：负贡献也应该保留。 最大路径和里负数分支会降低总和，向当前节点贡献时要和 0 取最大。
追问：直径返回边数还是节点数？ 常见定义返回边数，leftDepth + rightDepth 即可；若题目要节点数，再在结果口径上加 1。
追问：为什么必须后序？ 当前节点要依赖左右子树的深度或最大贡献，只有后序能先算子树再结算当前节点。

八、伪代码与不变量

数据结构题最好把操作过程写成伪代码，因为指针、索引或状态变化一旦说不清，就容易在边界用例上出错。以如何求二叉树的直径和最大路径和？为例，可以先固定不变量，再解释每一步为什么保持它。

初始化：维护结构不变量 invariant
遍历/调整：每处理 1 个节点或元素，都只改变必要指针/索引
校验：操作后结构仍满足顺序、连通性或堆/树性质
复杂度：每个元素最多进入/离开结构 O(1) 或 O(log n) 次

九、一步步推演与边界

回答如何求二叉树的直径和最大路径和？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

七、加强记忆

直径和最大路径和是同一套树形 DP模板：后序递归，用全局变量记录「以每个节点为拐点、左+当前+右」的最优解，而递归返回值只能带单边 当前 + max(左,右)（往上传不能分叉）。核心口诀：算答案可拐弯、往上传走直线。路径和额外要舍弃负贡献（和 0 取大），且 maxSum 初值设最小值。

简化版

详细版