There are only a few iterative solutions for this problem. Here I share an iterative one.
The idea is to use post-order traversal. If a node's children have all been visited, that node is labelled as 'visited'. Lists are used to pass path sum of left / right sub-trees and then pass value up.
The code uses the knowledge that no test case of empty tree.
import sys class Solution(object): def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ maxPathSum = -sys.maxint - 1 stack = [(root, False, , , )] while stack: node, visited, parent, left, right = stack.pop() if visited: # all children visited, update parent value, ignore negative values parent = max(max(left, right) + node.val, 0) # update maximum path sum maxPathSum = max(maxPathSum, left + right + node.val) else: # not visited, push back onto stack, set visited to True stack.append((node, True, parent, left, right)) # push right and left child onto stack if node.right: stack.append((node.right, False, right, , )) if node.left: stack.append((node.left, False, left, , )) return maxPathSum