Share my iterative Python solution (post-order traversal)


  • 0
    D

    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, [0], [0], [0])]
            while stack:
                node, visited, parent, left, right = stack.pop()
                if visited:
                    # all children visited, update parent value, ignore negative values
                    parent[0] = max(max(left[0], right[0]) + node.val, 0)
                    # update maximum path sum
                    maxPathSum = max(maxPathSum, left[0] + right[0] + 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, [0], [0]))
                    if node.left:
                        stack.append((node.left, False, left, [0], [0]))
    
            return maxPathSum

Log in to reply
 

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