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)