Easy to Understand Python Iterative Code(52ms)


  • 0
    K

    Inorder traversal is left->root->right so we need to visit all left nodes first, if they exist before printing the current node and then visiting the right.
    -Keep a flag to determine if the left has already been visited.
    -If not, insert the currentnode back into the stack, and insert it's left node(if it exist) ontop of the stack. Mark the currentnode as having visited left.
    -If the currentnode has visited left, add its value to the result array, and insert it's right node if it exists.

     ```class Solution(object):
    def inorderTraversal(self, root):
        if root is None:
            return []
        
        visited_left, res, stack = dict(), [], [root]
        while stack:
            n = stack.pop(0)
            if n not in visited_left:
                visited_left[n] = True
                stack.insert(0, n)
                if n.left:
                    stack.insert(0, n.left)
            else:
                res.append(n.val)
                if n.right:
                    stack.insert(0,n.right)
        return res ```

Log in to reply
 

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