Very simple iterative Python solution


  • 29
    C

    Classical usage of stack's LIFO feature, very easy to grasp:

    def preorderTraversal(self, root):
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return ret

  • 5
    C
    def preorderTraversal(self, root):
        if root is None:
            return []
        stack, result, cur = [], [], root
        while cur or stack:
            if not cur:
                cur = stack.pop()
            while cur:
                result.append(cur.val)
                if cur.right:
                    stack.append(cur.right)
                cur = cur.left
        return result
    

    I borrowed the idea from Iterative solution on Inorder traversal, which only pushes nodes from left on stack. For preorder, we only need to push right node on stack.


  • 0
    L

    Very simple to follow, thanks for posting.


  • 0
    Y

    Mine is similar to your idea.

    def preorderTraversal(self, root):
            stack=[]
            res=[]
            while stack or root:
                if root:
                    stack.append(root)
                    res.append(root.val)
                    root=root.left
                else:
                    root=stack.pop()
                    root=root.right
            return res
    

Log in to reply
 

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