# Simple Post Order Traversal Solution.

• ``````    def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# Not assuming there are no negetives.
# One stack post order traversal.
stack = []
current = root
dic = {}
self.za_best = -float('inf')
while True:
while current:
stack.append(current)
current = current.left
if not stack:
break
leftiest = stack[-1]
if not leftiest.right:
visit = leftiest
self.visiting(visit, dic)
stack.pop()  # pop out the 'leftiest' node.
while stack and stack[-1].right == visit:
visit = stack[-1]
self.visiting(visit, dic)
stack.pop()
else:
current = leftiest.right
return self.za_best

def visiting(self, node, dic):
if node.left and node.right:
left_best_path_val = dic[node.left]
right_best_path_val = dic[node.right]
both_left_and_right = left_best_path_val + right_best_path_val + node.val # This value cannot be used by other nodes.
self.za_best = max(self.za_best, both_left_and_right)
best_straight = max(left_best_path_val+node.val, right_best_path_val + node.val, node.val)
self.za_best = max(self.za_best, best_straight)
dic[node] = best_straight
elif node.left:
left_best_path_val = dic[node.left]
best_straight = max(left_best_path_val+node.val, node.val)
self.za_best = max(self.za_best, best_straight)
dic[node] = best_straight
elif node.right:
right_best_path_val = dic[node.right]
best_straight = max(right_best_path_val + node.val, node.val)
self.za_best = max(self.za_best, best_straight)
dic[node] = best_straight
else:
# Is leaf.
dic[node] = node.val
self.za_best = max(self.za_best, node.val)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.