网站首页图片素材长图,中国十大网站域名,安阳县有多少个乡镇,唐山市城市建设规划局网站为了找到二叉树的最大路径和#xff0c;我们需要考虑所有可能的路径#xff0c;包括不经过根节点的路径#xff0c;所以其实如果你从整体上来一条路径一条路径的遍历#xff0c;太复杂#xff0c;我们可以换个思路#xff0c;从每个节点出发#xff0c;就把那个节点当成…
为了找到二叉树的最大路径和我们需要考虑所有可能的路径包括不经过根节点的路径所以其实如果你从整体上来一条路径一条路径的遍历太复杂我们可以换个思路从每个节点出发就把那个节点当成根节点考虑以这个节点为根的最大路径和。这个路径可能只包含左子树或者右子树或者左右子树都包含。
这里有个很重要的点当考虑一个节点时我们实际上只关心以它为根的子树中通过它的最大路径和不需要知道这条路的完整细节只需要知道这个最大值是多少。
所以我们用递归和回溯的思想来解决这道题 定义一个辅助函数该函数将返回以当前节点为根的子树中通过当前节点的最大单边路径和即只向左或只向右延伸的最大路径和以及通过当前节点的最大路径和可能包括左子树和右子树。但是对于全局的最大路径和我们只需要考虑单边路径和因为全局最大路径可能不经过根节点。 递归逻辑 递归地计算左子树和右子树的最大单边路径和。如果左子树或右子树的最大单边路径和为负我们可以选择不将其包括在路径中因为加入负值会降低路径和。计算通过当前节点的最大路径和如果左右子树的最大单边路径和都非负则包括它们否则只包括非负的那一边。更新全局最大路径和只考虑单边路径和。 回溯在递归返回之前需要撤销对当前节点状态的影响因为我们需要从多个不同的路径来考虑问题。 初始化全局最大路径和初始化为最小整数值例如Integer.MIN_VALUE因为路径和至少为负数只有一个负节点时。但在实际应用中由于题目说明节点值为0到9我们可以初始化为比任何可能的单个节点值都小的数如-1如果确信树不为空。 返回返回全局最大路径和
代码如下
import javax.swing.tree.TreeNode;public class maxPathSum {// 二叉树中最大路径和// 二叉树的路径被定义为一条节点序列同一个节点在一条路径序列中至多出现一次 该路径至少包含一个节点且不一定经过根节点// 返回其最大路径和 注意节点值可能是负数class Solution{private int maxSumInteger.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}private int maxGain(TreeNode node){if(nodenull){return 0;}// 递归获得左右子树的单边路径和int leftGainMath.max(maxGain(node.left),0);int rightGainMath.max(maxGain(node.right),0);// 通过当前节点的最大路径和可能是左根右但只计算单边为正的情况int priceNewPathnode.valleftGainrightGain;// 更新全局最大路径和maxSumMath.max(maxSum,priceNewPath);// 返回以当前节点为根的最大单边路径和return node.valMath.max(leftGain,rightGain);}}// 注意maxGain返回的是以当前节点为根的子树中通过当前节点的最大单边路径和但这对于找到全局最大路径和是足够的// 我们不需要知道全局最大路径的确切路径只需要知道它的和是多少。}
