Simple iterative python solution with explanations - 56ms


  • 1
    S
    class Solution:
        # @param {TreeNode} root
        # @return {integer[]}
        def inorderTraversal(self, root):
            if root is None: return []
            results = []
            stack = []
            stack.append((False, root))
            while stack:
                (visited_left, node) = stack.pop()
                if not visited_left:
                    # now this node has gone to left
                    stack.append((True, node))
                    if node.left:
                        stack.append((False, node.left))
                else:
                    # We are done with the left side
                    # read the data
                    # go right
                    results.append(node.val)
                    if node.right:
                        stack.append((False, node.right))
    
            return results

  • 2
    C

    A shorter iterative Python solution:

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

Log in to reply
 

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