Simple 9-line python solution


  • 0
    Y
        def postorderTraversal(self, root):
             if not root: return []
             stack = [root]
             res = []
             while stack:
                 cur = stack.pop()
                 if cur.left: stack.append(cur.left)
                 if cur.right: stack.append(cur.right)
                 res.append(cur.val)
             return res[::-1]

  • 0

    Quadratic runtime, ouch. Better try doing it in linear time.


  • 0
    Y

    Thank you for your comment. May I ask if the quadratic runtime comes from "res = [cur.val] + res"? Thank you very much.


  • 0

    Yes, that's it. Because every time it creates a new list and copies the entire old list.


  • 0
    Y

    i got it. Thanks for your nice comment.


Log in to reply
 

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