Advertisement
imashutosh51

Maximum path sum from any node

Jul 31st, 2022 (edited)
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. /*
  2. for each node there can be four ways that the max path goes through the node:
  3. 1)Node only
  4. 2)Max path through left child+node
  5. 3)max path  through right child + node
  6. 4)max path through left child+node+max path through right child
  7. Note: updating max without including the root with only n1 and n2 is not the current node responsibility,it would have
  8. been already done on the descendent node.
  9. */
  10. int fun(Node *root,int &ans){
  11.     if(root==NULL) return 0;
  12.     int t1=0,t2=0;
  13.     if(root->left){
  14.         t1=fun(root->left,ans);
  15.     }
  16.     if(root->right) t2=fun(root->right,ans);
  17.     int path_with_one_child=max(max(t1,t2)+root->data,root->data);  //first threee condition will be checked here  
  18.     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
  19.     ans=max(ans,max_path_with_root);   //max path updated here
  20.     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
  21. }                               //considering other node as top most root node
  22.  
  23. class Solution {
  24.   public:
  25.     //Function to return maximum path sum from any node in a tree.
  26.     int findMaxSum(Node* root){
  27.        int ans=INT_MIN;
  28.           int temp=fun(root,ans);
  29.        return ans;
  30.     }
  31. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement