力扣124. 二叉树中的最大路径和
力扣124. 二叉树中的最大路径和
老规矩，原题
今天这道力扣划到困难，但是我觉得其实还好，当然前提是要刷过类似思路的问题。正好前几天做过一道类似的，不过我忘了哪题了。原题会给出一个二叉树。这个二叉树的每个节点上都带有一个数字，我们需要找到一个路径让这个路径上的所有节点的数字加起来最大。这个路径可以从树中的任意节点开始，也可以在树中的任意节点结束，但是路径上必须至少包含一个节点，并且路径上的每个节点至多只能出现一次。
看了一下题目，我一下就有了思路。需要有一条路径，那这条路径肯定有一个最高的祖先节点，这个路径之所以最长，是因为这个祖先节点的左子树和右子树的路径的节点最大，所以我们可以从低向上，一直统计到当前节点的左右子树的路径的最大值，再加上当前节点的值。就得到了这条路径的最大值，但是左右的最大值有可能是负数，所以要将这个和与当前节点做一下比较，如果当前节点的值更大，说明当前节点可能是这个最大路径的起点或终点。当然也可能是一个中间节点，这种情况是，当前节点的左子树或者右子树的路径和是负数，于是我们要舍弃一个子树，只和另外一个子树相加。当前节点也是其祖先的左或者右子树，所以需要返回回去。我们使用递归实现代码，以下是我的代码：
class Solution {
private int maxPathSumMax=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
int maxPathSum2 = maxPathSum2(root);
return Math.max(maxPathSumMax, maxPathSum2);
}
public int maxPathSum2(TreeNode root){
if (root == null) {
return 0;
}
int left =maxPathSum2(root.left);
int right = maxPathSum2(root.right);
maxPathSumMax=Math.max(Math.max(maxPathSumMax,root.val+left+right),root.val);
maxPathSumMax=Math.max(maxPathSumMax,root.val+left);
maxPathSumMax=Math.max(maxPathSumMax,root.val+right);
return Math.max(root.val+Math.max(left,right),root.val);
}
}
提交打败百分之99.99。代码很短，算法时间复杂度和空间复杂度都是线性。递归理解起来可能会有点困难，好好看一下，实在不能理解可以评论区留言。
力扣124. 二叉树中的最大路径和
https://www.than.pw/archives/%E5%8A%9B%E6%89%A3124.-%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E7%9A%84%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C