message: Update binary-tree-maximum-path-sum.py
diff: @@ -9,19 +9,44 @@ class TreeNode(object):
  class Solution(object):
  - maxSum = float("-inf")
  -
  # @param root, a tree node
  # @return an integer
  def maxPathSum(self, root):
  - self.maxPathSumRecu(root)
  - return self.maxSum
  + def iter_dfs(node):
  + result = float("-inf")
  + max_sum = [0]
  + stk = [(1, [node, max_sum])]
  + while stk:
  + step, params = stk.pop()
  + if step == 1:
  + node, ret = params
  + if not node:
  + continue
  + ret1, ret2 = [0], [0]
  + stk.append((2, [node, ret1, ret2, ret]))
  + stk.append((1, [node.right, ret2]))
  + stk.append((1, [node.left, ret1]))
  + elif step == 2:
  + node, ret1, ret2, ret = params
  + result = max(result, node.val+max(ret1[0], 0)+max(ret2[0], 0))
  + ret[0] = node.val+max(ret1[0], ret2[0], 0)
  + return result
  +
  + return iter_dfs(root)
  - def maxPathSumRecu(self, root):
  - if root is None:
  - return 0
  - left = max(0, self.maxPathSumRecu(root.left))
  - right = max(0, self.maxPathSumRecu(root.right))
  - self.maxSum = max(self.maxSum, root.val + left + right)
  - return root.val + max(left, right)
  +# Time: O(n)
  +# Space: O(h), h is height of binary tree
  +class Solution2(object):
  + # @param root, a tree node
  + # @return an integer
  + def maxPathSum(self, root):
  + def dfs(node):
  + if not node:
  + return (float("-inf"), 0)
  + max_left, curr_left = dfs(node.left)
  + max_right, curr_right = dfs(node.right)
  + return (max(max_left, max_right, node.val+max(curr_left, 0)+max(curr_right,0)),
  + node.val+max(curr_left, curr_right, 0))
  +
  + return dfs(root)[0]
  