Python Inorder Traversal


  • 0
    class Solution(object):
        def inorderTraversal(self, root):
            ans = []
            def recursive(r):
                if not r:
                    return 
                recursive(r.left)
                ans.append(r.val)
                recursive(r.right)
            recursive(root)
            return ans
    

  • 0
    M

    @Ipeq1 but this is recursive and the instructions said implement it iteratively


  • 1

    @marcmoy
    Thanks for pointing out, here is the iterative solution.

    class Solution(object):
        def inorderTraversal(self, root):
            ans, queue = [], []
            while root:
                queue.append(root)
                root = root.left
            while queue:
                top = queue.pop()
                ans.append(top.val)
                tmp = top.right
                while tmp:
                    queue.append(tmp)
                    tmp = tmp.left
            return ans
    

  • 0
    C

    @Ipeq1 The varible queue seems to work like a stack?


Log in to reply
 

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