AlgoPressAppearance
0124-二叉树中的最大路径和
https://leetcode.cn/problems/binary-tree-maximum-path-sum
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1： 
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2： 
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000
基本思路
我们选择一个节点，那么到选中这个节点后的最大路径和 就是 左节点的单边最大和 + 右节点的单边最大和 + 这个节点的值 通过递归求取单边的最大和，在中途我们会求当前节点最大路径和 maxPathSum ，遇到比 maxPathSum 大的值，则更新 maxPathSum
参考代码
csharp
public class Solution {
int maxPathSum = int.MinValue;
private int sideMax(TreeNode node){
if(node == null){
return 0;
}
int left = Math.Max(0,sideMax(node.left)); //如果是负数就舍弃
int right = Math.Max(0,sideMax(node.right)); //如果是负数就舍弃
//更新 maxPathSum
maxPathSum = Math.Max(maxPathSum, left + right + node.val);
return Math.Max(left,right)+node.val;
}
public int MaxPathSum(TreeNode root) {
sideMax(root);
return maxPathSum;
}
}
深度搜索，代码同上
csharp
public class Solution {
int maxPathSum = int.MinValue;
//深度优先求路径和
private int dfs(TreeNode root){
if(root == null){
return 0;
}
int left = Math.Max(0,dfs(root.left));
int right = Math.Max(0,dfs(root.right));
maxPathSum = Math.Max(maxPathSum,root.val + left + right); //最大路径和
int maxPath = root.val + Math.Max(left,right); //最大路径
return maxPath;
}
public int MaxPathSum(TreeNode root) {
dfs(root);
return maxPathSum;
}
}