Binary Tree Maximum Path Sum - LeetCode

PHOTO EMBED

Sat May 29 2021 16:45:25 GMT+0000 (UTC)

Saved by @Randumkeng

class Solution {
    int maxx=INT_MIN;
public:
    
    int ans(TreeNode* root)
    {
        if(root==NULL)return 0;
        int l = ans(root->left);
        int r = ans(root->right);
        maxx = max(maxx,l+r+root->val);
        return max(0,max(l+root->val,r+root->val));
    }
    int maxPathSum(TreeNode* root) {
        int pathSum = ans(root);
        return maxx;
    }
};
content_copyCOPY

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any path.

https://leetcode.com/problems/binary-tree-maximum-path-sum/