【算法3】二叉树中的最大路径和

二叉树中的最大路径和给定一棵非空二叉树路径由相邻节点组成每个节点最多经过一次。路径不必经过根节点也不必从叶子节点开始或结束。例如在下面的二叉树中最大路径是15 → 20 → 7最大路径和是15 20 7 42。-10 / \ 9 20 / \ 15 7一、解题思路当前节点必须先得到左右子树的计算结果所以采用“左子树、右子树、当前节点”的后序遍历。递归函数maxGain(root)的返回值不是整棵树的最大路径和而是“从当前节点出发只向一侧延伸时能够返回给父节点的最大路径和”。对于当前节点左、右子树的贡献分别为leftGain和rightGain。如果某个贡献是负数连接这棵子树只会使路径和变小因此通过Math.max(0, 子树贡献)将它舍弃。一条路径如果在当前节点处结束可以同时连接左右两侧所以用root.val leftGain rightGain更新全局变量maxSum。但当前节点向父节点返回时路径还要继续向上连接不能同时保留左右两侧否则路径会产生分叉。因此只能返回root.val Math.max(leftGain, rightGain)。以节点20为例左右子树分别返回15和7。经过节点20的完整路径和是15 20 7 42所以用42更新maxSum而节点20返回给父节点时只能选择较大的一侧因此返回20 max(15, 7) 35。两种结果的职责不同root.val leftGain rightGain 用于更新整棵树的最大路径和 root.val max(leftGain, rightGain) 用于返回给父节点继续计算全局变量maxSum必须初始化为Integer.MIN_VALUE。如果整棵树都是负数最大路径和应当是其中最大的节点值而不是0。二、完整代码publicclassBinaryTreeMaximumPathSum{staticclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intval){this.valval;}}/** * 遍历过程中发现的最大完整路径和。 */privateintmaxSum;publicintmaxPathSum(TreeNoderoot){maxSumInteger.MIN_VALUE;// 启动后序遍历递归过程中会更新 maxSum。maxGain(root);returnmaxSum;}/** * 返回从当前节点出发只向一侧延伸时 * 能够提供给父节点的最大路径和。 */privateintmaxGain(TreeNoderoot){if(rootnull){return0;}intleftGainMath.max(0,maxGain(root.left));intrightGainMath.max(0,maxGain(root.right));// 完整路径可以同时连接左右两侧。intcurrentPathSumroot.valleftGainrightGain;maxSumMath.max(maxSum,currentPathSum);// 返回父节点时只能选择一侧。returnroot.valMath.max(leftGain,rightGain);}publicstaticvoidmain(String[]args){/* * -10 * / \ * 9 20 * / \ * 15 7 */TreeNoderootnewTreeNode(-10);root.leftnewTreeNode(9);root.rightnewTreeNode(20);root.right.leftnewTreeNode(15);root.right.rightnewTreeNode(7);BinaryTreeMaximumPathSumsolutionnewBinaryTreeMaximumPathSum();intresultsolution.maxPathSum(root);System.out.println(最大路径和result);}}程序输出最大路径和42每个节点只计算一次所以时间复杂度为O(n)递归调用栈的最大深度等于树高所以空间复杂度为O(h)。三、压栈、出栈与返回父节点程序首先进入maxPathSum(-10)将maxSum初始化为最小整数然后调用maxGain(-10)。此时maxPathSum暂停等待整棵树递归结束。栈顶 ┌──────────────────────────┐ │ maxGain(-10) │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底maxGain(-10)先计算左子树因此调用maxGain(9)。节点-10的栈帧不会消失而是留在栈中等待左子树返回。栈顶 ┌──────────────────────────┐ │ maxGain(9) │ ├──────────────────────────┤ │ maxGain(-10)等待左结果 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底节点9的左右子树都是空节点所以leftGain 0、rightGain 0。经过节点9的完整路径和为9 0 0 9因此将maxSum更新为9随后节点9向父节点-10返回9 max(0, 0) 9并从调用栈中弹出。栈顶 ┌──────────────────────────┐ │ maxGain(-10) │ │ leftGain 9 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底 maxSum 9得到左子树结果后maxGain(-10)调用maxGain(20)计算右子树。节点20又先调用maxGain(15)因此栈中依次保存根节点和正在等待结果的父节点。栈顶 ┌──────────────────────────┐ │ maxGain(15) │ ├──────────────────────────┤ │ maxGain(20)等待左结果 │ ├──────────────────────────┤ │ maxGain(-10)等待右结果 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底节点15没有孩子所以经过它的完整路径和是15maxSum从9更新为15。节点15向父节点20返回15然后出栈。回到节点20后leftGain 15。接着调用maxGain(7)计算右子树栈顶 ┌──────────────────────────┐ │ maxGain(7) │ ├──────────────────────────┤ │ maxGain(20)等待右结果 │ ├──────────────────────────┤ │ maxGain(-10)等待右结果 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底节点7没有孩子所以向父节点20返回7然后出栈。此时节点20已经得到leftGain 15和rightGain 7。栈顶 ┌──────────────────────────┐ │ maxGain(20) │ │ leftGain 15 │ │ rightGain 7 │ ├──────────────────────────┤ │ maxGain(-10)等待右结果 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底经过节点20的完整路径和是15 20 7 42所以maxSum更新为42。节点20向父节点-10返回时只能选择一侧因此返回20 max(15, 7) 35然后出栈。回到根节点-10后左右子树的返回值分别是9和35。栈顶 ┌──────────────────────────┐ │ maxGain(-10) │ │ leftGain 9 │ │ rightGain 35 │ ├──────────────────────────┤ │ maxPathSum等待递归结束 │ └──────────────────────────┘ 栈底 maxSum 42经过根节点的完整路径和是9 (-10) 35 34小于当前的42所以maxSum不变。根节点还会计算单边返回值-10 max(9, 35) 25但根节点没有父节点所以这个返回值没有被使用。maxGain(-10)出栈后程序回到maxPathSum。栈顶 ┌──────────────────────────┐ │ maxPathSum │ │ maxSum 42 │ └──────────────────────────┘ 栈底最后maxPathSum返回maxSum结果为42。整个过程只有一条数据链子节点返回单边贡献 ↓ 父节点组合左右贡献 ↓ 更新全局最大路径和 ↓ 父节点再返回自己的单边贡献maxGain的返回值供父节点继续计算maxSum记录遍历过程中出现的最大完整路径maxPathSum在递归结束后返回最终结果。