Easy to Understand Python Iterative Code(52ms)

  • 0

    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)
                if n.right:
        return res ```

Log in to reply

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