Btree max path sum

Posted on |

leetCode 124. the first idea is recursive from root to bottom leaf, and return the max from left or right at each node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int subsum(TreeNode* node)
{
	int max_left = 0, max_right =0;
	if(node->left)
		max_left = subsum(node->left);
	else
		return std::max(node->val, subsum(node->right));
	if(node->right)
		max_right = subsum(node->right);
	else
		return std::max(node->val, subsum(node->left));
	sum += node->val + std::max(max_left, max_right); 
	return sum;
}

this will get the max sum branch from top to bottom, but can’t consider the other branch, and there is case when the max sum branch is actually smaller than a subtree sum. so here needs to consider the subtree sum as well, since the root tree can be consider as a subtree, so after implmenting subtree sum, actually no need to consider the other branch sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int subsum(TreeNode*  node, std::priority_queue<int, vector<int>, greater<int> >& s)
{
 if(node==nullptr)
	 return 0;
 
 int max_left=0, max_right=0;
 int sum=0; 
 int subtree_sum = 0; 
 if(node->left){
	 max_left = subsum(node->left, s); 
	 subtree_sum += max_left;  
 }else
 {
	 subtree_sum += node->val; 
	 return std::max(node->val,  subsum(node->right, s)); 
 }
	 
 if(node->right){
	 max_right = subsum(node->right, s);
	 subtree_sum += max_right;  
 }else{
	 subtree_sum += node->val; 
	 return std::max(node->val, subsum(node->left, s)); 
 }
 
 sum += node->val + std::max(max_left, max_right);
 if(node->right != nullptr  || node->left != nullptr)
	subtree_sum += node->val; 
 else
	 subtree_sum -= node->val; 
 
 if(subtree_sum > sum){
	 s.push(subtree_sum); 
	 cout << "s.top= " << s.top() << "\n" << endl; 
	 while( sum > s.top())
	 {
		 s.pop();
	 }
 }
 return sum; 
}

passing priority_queue s as reference, so if subtree\_sum is bigger than the top-bottom branch sum, then it will be pushed into s; but pop out the elements smaller than current branch sum in each recrusive routing.

finally, compare the largest elemnet in s with top-bottom branch sum.