/**
* 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) {
int
maxSum = Integer.MIN_VALUE;
if(root != null){
Stack<TreeNode> sta = new
Stack<TreeNode>();
HashSet<TreeNode> hset = new
HashSet<TreeNode>();
sta.push(root);
hset.add(root);
while(!sta.empty()){
TreeNode aNode = sta.pop();
if(aNode.left != null
&& hset.add(aNode.left)){
sta.push(aNode);
sta.push(aNode.left);
}
else
if(aNode.right != null
&& hset.add(aNode.right)){
sta.push(aNode);
sta.push(aNode.right);
}
else{
int
leftMax = (aNode.left == null) ? 0
: aNode.left.val;
int
rightMax = (aNode.right == null) ? 0
: aNode.right.val;
int
sum = aNode.val + leftMax + rightMax;
aNode.val = Math.max(aNode.val, Math.max(leftMax + aNode.val, rightMax + aNode.val));
maxSum = Math.max(maxSum, Math.max(aNode.val, sum));
}
}
}
return
maxSum;
}
}
