LeetCode: Binary Tree Maximum Path Sum

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.

这个题让我做的有点儿恶心了

算法本身不难，瞬间找到solution: DFS recursion，题目要求有些变态， the value of a node can be positive, 0 and negative. 

Key points:

•  Use a member variable maxSum. If c++, can use " int maxPathSumRe(TreeNode *root, int &max)"
•  return value should be Maximum(left, right) + curVal

 Code  

	public class Solution {
	int maxSum;
	public int maxPathSum(TreeNode root) {
	if(root == null) return 0;
	if(root.left == null && root.right == null) return root.val;
	maxSum = root.val;
	maxPathSumRe(root);
	return maxSum;
	}
	public int maxPathSumRe(TreeNode root){
	if(root == null) return 0;
	// if(root.left == null && root.right == null) return root.val;
	// if don't comment out this statement, tons of conditions should be considered. it's like a nightmare.
	int rightVal = maxPathSumRe(root.right);
	int leftVal = maxPathSumRe(root.left);
	int curVal = root.val;
	if(rightVal>0) curVal +=rightVal;
	if(leftVal>0) curVal +=leftVal;
	maxSum = Math.max(maxSum, curVal);
	/*
	if(rightVal <=0){
	if(leftVal <=0){
	maxSum = Math.max(maxSum, root.val);
	}
	else{
	maxSum = Math.max(maxSum, leftVal+root.val);
	}
	}
	else{
	if(leftVal <=0){
	maxSum = Math.max(maxSum, rightVal+root.val);
	}
	else{
	maxSum = Math.max(maxSum, rightVal+leftVal+root.val);
	}
	}
	*/
	int maxChild = Math.max(rightVal, leftVal);
	if(maxChild <= 0 ) return root.val;//discard children nodes
	else return maxChild + root.val;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub