Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- for each node there can be four ways that the max path goes through the node:
- 1)Node only
- 2)Max path through left child+node
- 3)max path through right child + node
- 4)max path through left child+node+max path through right child
- Note: updating max without including the root with only n1 and n2 is not the current node responsibility,it would have
- been already done on the descendent node.
- */
- int fun(Node *root,int &ans){
- if(root==NULL) return 0;
- int t1=0,t2=0;
- if(root->left){
- t1=fun(root->left,ans);
- }
- if(root->right) t2=fun(root->right,ans);
- int path_with_one_child=max(max(t1,t2)+root->data,root->data); //first threee condition will be checked here
- int max_path_with_root=max(path_with_one_child,t1+t2+root->data); //max path possible with this node as top most root of path is found here ie. 4th condition
- ans=max(ans,max_path_with_root); //max path updated here
- return path_with_one_child; //we are passing path generated only through condition 1,2 and 3 because only that can help to create some other max path
- } //considering other node as top most root node
- class Solution {
- public:
- //Function to return maximum path sum from any node in a tree.
- int findMaxSum(Node* root){
- int ans=INT_MIN;
- int temp=fun(root,ans);
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement