LeetCode Q124: Binary Tree Maximum Path Sum (hard)

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution:

Using recursion and compute the maximum path under each node. For each node return the current maximum path passing the node.

	int helper(TreeNode* root, int& maxSum){
	if(root==NULL)
	return 0;
	int l = helper(root->left, maxSum);
	int r = helper(root->right, maxSum);
	int sum = max(max(0, l+root->val), max(0, r+root->val));
	maxSum = max(maxSum, l+r+root->val);
	return sum;
	}
	int maxPathSum(TreeNode* root) {
	int res=INT_MIN;
	if(root==NULL)
	return res;
	helper(root, res);
	return res;
	}

view raw Q124:BinaryTreeMaximumPathSum.cpp hosted with ❤ by GitHub