题目
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6 示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
解析
想到left的最大路径和right的最大路径求完之后更新最终结果的状态。思考递归子问题的代码的构造。会发现两个关键问题：
1.递归需要记录下来左右子树经过根节点的最大值，以便计算后面的父节点，对应代码即：
return Math.Max(leftSum, rightSum) + node.val;
- 递归还要记录下经过根节点的最大值
maxSum = Math.Max(lefSum + rightSum + node.val, maxSum);
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int maxSum = 0;
/// <summary>
/// 传递的是经过左子树和右子树的根节点的和
/// </summary>
/// <returns></returns>
int Helper(TreeNode node)
{
if (node == null) return 0;
int lefSum = Math.Max(Helper(node.left), 0);
int rightSum = Math.Max(Helper(node.right), 0);
//更新
maxSum = Math.Max(lefSum + rightSum + node.val, maxSum);
//递归
return Math.Max(lefSum, rightSum) + node.val;
}
public int MaxPathSum(TreeNode root)
{
maxSum = int.MinValue;
Helper(root);
return maxSum;
}
}
