A relatively difficult tree problem. Well, a recursive solution still gives clean codes. The tricky part of this problem is how to record the result. You may refer to this link for a nice solution. The code is rewritten as follows.
class Solution { public: int maxPathSum(TreeNode* root) { sum = INT_MIN; pathSum(root); return sum; } private: int sum; int pathSum(TreeNode* node) { if (!node) return 0; int left = max(0, pathSum(node -> left)); int right = max(0, pathSum(node -> right)); sum = max(sum, left + right + node -> val); return max(left, right) + node -> val; } };
