Binary Tree Maximum Path Sum[leet code test cases passed]
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
answer: 6 (can be any arbitary traversal path)
Consider two cases at each Node:
1. via this node link left subtree and right subtree to find possible max sum. This node will be the root of the new path tree.
in this case update max
2. via this node link the subtree and its parent to form a path with nodes in higher level.
in this case return a local_max to its parent (this node must get involved in the path). The local_max has three possibilities: (1) this node + local_max of left child (2) this node + local_max of right child (3) only this node. Choose the maximum to return.
Updating max is irrelevant of where's the root of the path tree. The recursion just prints all the possible path with maximum sum on this level.
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int max=-9999;
helper(root,max);
return max;
}
//return local_max if this node should be linked to its parent
int helper(TreeNode *root, int& max)
{
if(root==NULL)
return -9999;
int sum_from_left_child = helper(root->left,max);
int sum_from_right_child = helper(root->right,max);
int local_max=0;
//if connect root to its parent and form a new path, choose either left or right local max
if(sum_from_left_child >= sum_from_right_child)
{
if(root->val < root->val + sum_from_left_child)
local_max=root->val + sum_from_left_child;
else
local_max=root->val;
}
else{
if(root->val < root->val + sum_from_right_child)
local_max=root->val + sum_from_right_child;
else www.zzzyk.com
local_max=root->val;
}
//update max
if(max < sum_from_right_child + root->val + sum_from_left_child)
max=sum_from_right_child + root->val + sum_from_left_child;
if(max < local_max)
max = local_max;
return local_max;
}
};
补充：综合编程 , 其他综合 ,
