124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

---

给定一个二叉树，要求树中某条路径的最大和。注意路径可以不经过叶子节点，也可以不经过根节点，即树中任意一条相连的路径即可。

使用递归的思路。对于一个节点，经过它的最大和路径有如下几种情况：

• 仅包含节点本身（当左、右、父亲节点的路径和都是负数时）
• 穿过该节点，且还会往该节点的父亲上面走，说明最优路径的跟在该节点上面，该节点的左子树或右子树路径构成了最优路径的一部分
• 没有穿过该节点，即该节点为最优路径的跟，则路径的两端可能是该节点的左右孩子

完整代码如下，辅助函数maxSum的返回值即为上面的前两种情况的最大值，maxSum返回之后有可能构成父节点的最大和。ans则是全局的最大和，还包括上面列的第三种情况。

class Solution {
public:
	int maxSum(TreeNode *root, int &ans) {
		if (root == NULL)return 0;
		int left_sum = maxSum(root->left, ans), right_sum = maxSum(root->right, ans);

		// 经过root节点的子树，还得往root的父亲上面走
		int left_or_right_root = max(root->val, root->val + max(left_sum, right_sum));

		// 最后一项是以root为根，左右子树都走，即不往root的父亲上面走
		ans = max(ans, max(left_or_right_root, root->val + left_sum + right_sum));

		return left_or_right_root;
	}
	int maxPathSum(TreeNode* root) {
		int ans = INT_MIN;
		maxSum(root, ans);
		return ans;
	}
};

本代码提交AC，用时36MS。