leetcode 124. 二叉树中的最大路径和

题目：124. 二叉树中的最大路径和 - 力扣（LeetCode）

定义一个节点的“最大单向路径和”是single，single有以下几种情况：

1. 只有该节点
2. 该节点+左儿子的single
3. 该节点+右儿子的single

设答案是节点 node 为根节点，有以下几种情况：

1. 只有根节点
2. 根节点+左儿子的single
3. 根节点+右儿子的single
4. 根节点+左儿子的single+右儿子的single

遍历全部节点，即可找到最大的答案

class Solution {
public:int ans;int maxPathSum(TreeNode* root) {ans = root->val;int single = 0;F(root, single);return ans;}void F(TreeNode* t, int& single) {if (!t) {single = 0;return;}int lsingle = 0;F(t->left, lsingle);int rsingle = 0;F(t->right, rsingle);if (t->val > ans) {ans = t->val;}single = t->val;if (t->left && lsingle > 0) {single = t->val + lsingle;}if (t->right && rsingle > 0 && t->val + rsingle > single) {single = t->val + rsingle;}if (single > ans) {ans = single;}if (lsingle + rsingle + t->val > ans) {ans = lsingle + rsingle + t->val;}}
};