94. Binary Tree Maximum Path Sum

class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ struct resType{ int root2Any; int any2Any; }; int maxPathSum(TreeNode * root) { // write your code here if(root == NULL){ return 0; } resType res = pathSum(root); return res.any2Any; } resType pathSum(TreeNode *root){ resType res; res.root2Any = INT_MIN; res.any2Any = INT_MIN; if(root == NULL){ return res; } resType left = pathSum(root->left); resType right = pathSum(root->right); res.root2Any = max(max(left.root2Any, right.root2Any), 0) + root->val; res.any2Any = max(max(left.any2Any, right.any2Any), root->val + max(left.root2Any, 0) + max(right.root2Any, 0)); return res; } };