int maxPathSum(TreeNode *root) {
int maxPath = INT_MIN;
dfsMaxPath(root, maxPath);
return maxPath;
}
int dfsMaxPath(TreeNode *root, int &maxPath) {
if (!root) return 0;
int l = max(0, dfsMaxPath(root>left, maxPath));
int r = max(0, dfsMaxPath(root>right, maxPath));
maxPath = max(maxPath, l + r + root>val);
return root>val + max(l, r);
}
A very concise recursive solution


Your code is nice. only seems" maxPath" is not necessary as an argument. ”maxPath“ is used in l and r before updating in
maxPath = max(maxPath, l + r + root>val)
, so there is no point considering ”maxPath“ . I modefy your code more intuitive.class Solution { public: int maxPath; int maxPathSum(TreeNode *root) { maxPath = INT_MIN; dfsMaxPath(root); return maxPath; } int dfsMaxPath(TreeNode *root) { if (!root) return 0; int l = max(0, dfsMaxPath(root>left)); int r = max(0, dfsMaxPath(root>right)); maxPath = max(maxPath, l + r + root>val); return root>val + max(l, r); } };


@allbugs said in A very concise recursive solution:
the time is O(n), but the rec
You are right. The time complexity is O(n). It is because every node is processed only once.
To calculate space complexity, let's try to simulate the stack manually for the tree 2>1>3(inoder sequece).
 First, root (1) is processed. ie. it is pushed into the stack.
 Then, root.left is processed. now stack has 1 and 2.
 Then when we do root.left again, it is null and hence we start popping out.
So at any instance, stack will only contain log n entries. This is for a balanced tree.
But for worst case space complexity, we usually consider a skewed tree. So considering a left skewed tree, it will contain all n elements in the stack before u start popping out. Therefore, the worst case space complexity would be O(n). Let me know, if it is otherwise.