本文概览本文以LeetCode题目二叉树中的最大路径和为例讲解拐点视角的思路——每个节点作为拐点更新全局最大值同时只传单边最大路径给父节点一、题目二、题目分析题目要求给定一棵二叉树找到路径和最大的路径。路径可以从任意节点出发到任意节点结束但必须沿着父子关系往下走不能分叉难点在于二叉树有左右两条分支一条路径可能只走左子树可能只走右子树也可能经过某个节点后同时走左右两棵子树这题的示例有一点误导性它写了15 → 20 → 7这样的箭头容易让人先入为主地以为路径有方向顺序从而联想到左→根→右的中序遍历。但实际上方向无所谓——题目完全可以写成20 → 15 → 7或7 → 20 → 15只要两个节点之间有连线它们就是连通的顺序不重要。所以不要被箭头误导成某种特定遍历方式思路概览Java 实现代码如下classSolution{privateintmaxSumInteger.MIN_VALUE;publicintmaxPathSum(TreeNoderoot){dfs(root);returnmaxSum;}privateintdfs(TreeNodenode){if(nodenull){return0;}// 递归计算左子树的最大路径和intleftMath.max(0,dfs(node.left));// 递归计算右子树的最大路径和intrightMath.max(0,dfs(node.right));// 更新最大路径和maxSumMath.max(maxSum,node.valleftright);// 返回当前节点的最大路径和returnnode.valMath.max(left,right);}}思路简要说明核心是拐点视角把每个节点看作一条路径的最高点拐点路径从这个节点的左子树上来经过这个节点再下到右子树。每个节点做两件事作为拐点更新全局最大值以当前节点为拐点的路径和 node.val 左子树最大路径 右子树最大路径和maxSum比大就更新作为子路径传给父节点父节点需要知道当前节点这条路径可不可以走只要是正数就有可能对父节点的路径有增益、有可能更新最大值所以要把当前节点的单边最大路径返回给父节点具体为什么返回单边下面详解说另一个关键点子树最大路径如果小于 0就当 0 处理Math.max(0, dfs(...))因为负数路径只会拉低总和不如不要这条子树三、思路详解第一步为什么要找拐点先看题目给的例子输入[-10, 9, 20, null, null, 15, 7] 输出42 解释最优路径是 15 - 20 - 7对应二叉树-10 / \ 9 20 / \ 15 7如果从整体去看这条路径15 → 20 → 7似乎很难找——二叉树有左右两条分支路径可能只走一边也可能两边都走到底怎么组合才能最大换个角度想这条路径有一个特点——它经过节点 20而 20 是这条路径在树里的最高点。路径从 20 的左子树15延伸过来经过 20再延伸到右子树7-10 / \ 9 20 ← 20 是这条路径的最高点 / \ 15 7任何一条路径在二叉树里都有且只有一个这样的最高点——从这个节点开始路径分别往左右两边延伸下去。我们把这个节点叫做拐点既然每条路径都有一个拐点那找最大路径和就转化成了对每个节点算出以它为拐点的路径和取最大值就是答案。这样就把一个整体问题拆成了对每个节点的局部问题第二步作为拐点——更新全局最大值对于任意一个节点如果它是某条路径的拐点那么这条路径的形态一定是左子树的某条路径 ← 当前节点 → 右子树的某条路径要使这条路径最大就要让左右两边的路径都最大。所以以当前节点为拐点的最大路径和 node.val 左子树最大路径 右子树最大路径20 / \ 15 7 以 20 为拐点的路径和 20 15 7 42这就是maxSum Math.max(maxSum, node.val left right)这行的含义——用当前节点作为拐点尝试更新全局最大值第三步作为子路径——传给父节点什么当前节点算完拐点路径和之后还要返回一个值给父节点。这里要理解一件事父节点也是拐点它也在算自己的拐点路径和比如节点 20 给父节点 -10 返回时-10 也在算以 -10 为拐点的路径和。-10 作为拐点它的路径形态是9 ← -10 → 20 这边。注意 -10 的右边只能接 20 的某一条路径——要么是 20→15 这条要么是 20→7 这条不能两条都接因为路径不能分叉-10 ← -10 是拐点右边只能接 20 的一条路径 / \ 9 20 ← 20 返回给 -10 的是单边最大路径 / \ 15 7所以 20 返回给 -10 的值应该是20 max(15, 7) 35即走左子树和走右子树中较大的那条这就是return node.val Math.max(left, right)的含义——返回单边最大路径和给父节点为什么只要是正数都要返回因为父节点作为拐点时它的路径和 父.val 左 右。只要当前节点返回的值是正数加到父节点上就能让父节点的拐点路径和更大有更新最大值的可能。所以正数路径对父节点来说是有益的必须返回第四步负数路径当 0 处理代码里有个细节int left Math.max(0, dfs(node.left))为什么要和 0 比较因为子树的最大路径和可能是负数。如果左子树整体都是负数那把左子树加进来只会拉低总和不如不要这条子树5 / -3 / \ -1 -2 5 的左子树最大路径 -3 (-1) 或 -3 (-2) 都是负数 如果加进来5 (-3) 2 如果不要5 0 5 ← 更大所以子树返回值小于 0 时直接当 0 处理相当于放弃这条子树对于拐点更新也是同理如果左右子树都是负数left0, right0拐点路径和 node.val 0 0 node.val也就是只要这个节点自己第五步完整执行过程以这棵树为例-10 / \ 9 20 / \ 15 7初始maxSum Integer.MIN_VALUE访问节点 9当前路径-10→9左子树 null → left 0右子树 null → right 0拐点更新maxSum max(MIN, 9 0 0) 9返回单边9 max(0, 0) 9访问节点 15当前路径-10→20→15左子树 null → left 0右子树 null → right 0拐点更新maxSum max(9, 15 0 0) 15返回单边15 max(0, 0) 15访问节点 7当前路径-10→20→7左子树 null → left 0右子树 null → right 0拐点更新maxSum max(15, 7 0 0) 15返回单边7 max(0, 0) 7访问节点 20当前路径-10→20left max(0, 15) 15right max(0, 7) 7拐点更新maxSum max(15, 20 15 7) 42 ← 找到最大值返回单边20 max(15, 7) 35访问节点 -10当前路径-10left max(0, 9) 9right max(0, 35) 35拐点更新maxSum max(42, -10 9 35) 42-10 拉低了没有更新返回单边-10 max(9, 35) 25最终结果maxSum 42对应路径 15 → 20 → 7关键点节点 20 作为拐点时算出了 42但传给父节点 -10 的只有单边 352015。因为如果 -10 是拐点它另一边只能留给自己不能让 20 两边都走第六步和最大子数组和的思路对比这道题和最大子数组和的思路本质上是相通的最大子数组和二叉树中的最大路径和关注点当前位置的头尾路径的最高点拐点当前状态以当前位置结尾的最大和以当前节点为拐点的最大路径和递推关系max(前一个和当前, 当前)node.val max(左, 0) max(右, 0)负数处理前缀和为负则重新开始子树为负则当 0 处理全局更新每个位置更新全局 max每个节点作为拐点更新全局 max核心都是不关注整条路径只关注当前位置的关键状态然后每一步都尝试更新全局最大值复杂度分析时间复杂度O(n)每个节点遍历一次空间复杂度O(h)递归栈深度等于树的高度最坏情况 O(n)