hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Binary Tree Maximum Path Sum
Problem: 124. Binary Tree Maximum Path Sum
Problem Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/
Approach:
Started traversing the binary tree from the root.
While moving toward the depth, we need to look for 3 things. For a root, we need to look for -
The maximum sum from the left sub-tree adds the value of the root say, Left_Sum.
The maximum sum from the right sub-tree adds the value of the root say, Right_Sum.
The sum of Left_Sum and Right_Sum adds the value of its root say, Whole_sum.
Take the maximum between Left_Sum, Right_Sum, and Whole_sum.
Return the maximum between Left_Sum and Right_Sum to its root.
Repeat the process until we traversal completes.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1) + Auxilary Stack
Code [C++]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int solve(TreeNode * root, int & ans){
if(!root) return 0;
int left = max(solve(root->left, ans), 0);
int right = max(solve(root->right, ans), 0);
ans = max(ans, left + right + root->val);
return max(left+root->val, right+root->val);
}
int maxPathSum(TreeNode* root) {
int ans = INT_MIN;
solve(root, ans);
return ans;
}
};