Simple python accepted 40ms iterative method


  • 0
    M

    Two key points:

    1. Stack (push right, then push left)
    2. Temporary variable to store last popped object, to determine whether to pop an intermediate node or push the children of the intermediate node

    Code:

    class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        
        stack = []
        lastPop = root
        stack.append(root)
        result = []
        
        l = len(stack)
        
        while(l>0):
            
            peek = stack[l-1]
            if peek.left == None and peek.right == None:
                pop = stack.pop()
                result.append(pop.val)
                lastPop = pop
            else:
                if lastPop == peek.left or lastPop == peek.right:
                    pop = stack.pop()
                    result.append(pop.val)
                    lastPop = pop
                else:
                    if peek.right != None:
                        stack.append(peek.right)
                    if peek.left != None:
                        stack.append(peek.left)
            #update l
            l = len(stack)
            
        return result

Log in to reply
 

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