Binary Tree Maximum Path Sum (Java)

Leetcode

Solution:

Preorderly  traverse the whole tree. For each  node calculate Max(root, root+leftSide, root+rightSide, leftSide+root+rightSide ), update max[0] (which is used to store max value), then return Max (root+leftSide, root+rightSide, root)

	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.
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public int maxPathSum(TreeNode root) {
	if (root==null){
	return 0;
	}
	int[] max={Integer.MIN_VALUE};
	maxPathSum(root, max);
	return max[0];
	}
	private int maxPathSum(TreeNode root, int[] max ){
	if (root==null){
	return 0;
	}
	max[0]=Math.max(max[0], root.val);
	int leftMax=maxPathSum(root.left, max)+root.val;
	max[0]=Math.max(leftMax, max[0]);
	int rightMax=maxPathSum(root.right, max)+root.val;
	max[0]=Math.max(rightMax, max[0]);
	max[0]=Math.max(rightMax+leftMax-root.val, max[0]);
	return Math.max(Math.max(leftMax, rightMax), root.val);
	}
	}

view raw Binary Tree Maximum Path Sum .java hosted with ❤ by GitHub