Binary Tree Maximum Path Sum leetcode cpp

 Binary Tree Maximum Path Sum leetcode cpp

 Binary Tree Maximum Path Sum leetcode cpp

Question Solution

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1

/ \

2 3

Return 6.

 

Maximum-Sum-path-between-two-leaves (1)

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int sum=INT_MIN;
int getMax(int a , int b , int c)
{
if(b < 0 && c < 0)
return a;
if(b<0)
return a+c;
if(c<0)
return a+b;
return (a+b+c);
}
int maxPathSumRec(TreeNode *root) {
int val1 =INT_MIN,val2=INT_MIN;

if(root == NULL) return 0 ;
int temp1=maxPathSumRec(root->left);
int temp2=maxPathSumRec(root->right);
if(max(temp1, temp2) > 0)
val1=root->val + max(temp1, temp2); // include root && either left/right
else
val1=root->val;
val2=getMax(root->val , temp1 , temp2);// include root && both left,right
if(val1 >sum)
sum=val1; //storing max sum as global
if(val2 > sum)
sum=val2;
return val1;
}
int maxPathSum(TreeNode *root) {
int val1 =INT_MIN;
val1=maxPathSumRec(root);
if(val1 >sum)
sum=val1;
return sum;
}

Depth of tree:

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
return max(maxDepth(root->left),maxDepth(root->right)) +1;
}
};

Same tree?

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q==NULL)
return true;
if(p == NULL && q!=NULL)
return false;
if(p != NULL && q==NULL)
return false;
return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

Leave a Reply

Your email address will not be published. Required fields are marked *