124. Binary Tree Maximum Path Sum

题意：

给一颗二叉树，寻找一个路径，满足路径上的节点值的和最大。这个路径可以是任意起点和任意终点。

思路：

后序递归，在每个节点处将其左右节点作为路径结尾且和大于0的左右子路径连接，判断新路径的和是否是最大。然后返回以该节点为结尾的最大路径。

int fuc(TreeNode* root, int &res) {
	if (!root)
		return 0;
	int l = max(fuc(root->left, res), 0), r = max(fuc(root->right, res), 0);
	res = max(res, root->val + l + r);

	return root->val + max(l, r);
}

int maxPathSum(TreeNode* root) {
	int res = INT_MIN;
	fuc(root, res);
	return res;
}