Simple Python iterative solution by using a visited flag - O(n) 56ms

  • 19
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # @param {TreeNode} root
        # @return {integer[]}
        def inorderTraversal(self, root):
            result, stack = [], [(root, False)]
            while stack:
                cur, visited = stack.pop()
                if cur:
                    if visited:
                        stack.append((cur.right, False))
                        stack.append((cur, True))
                        stack.append((cur.left, False))
            return result

  • 0

    Great solution. can you extend such methods to pre-order and post-order search?

  • 0

    i like it ~ thank you~

  • 0

    Could you explain why go node.right first and then node.left? since for the recursive code, it's node.left, res.append(node.val), node.right. Why is it the other way around for iterative

  • 0

    @pennlio Simply change (cur.right, cur, cur.left) triplet

    in-order: (cur.right, cur, cur.left)
    pre-order: (cur.right, cur.left, cur)
    post-order: (cur, cur.right, cur.left)

  • 0

    Brilliant answer. Easy to extend to pre-order and post-order cases.
    I wonder why this answer has so few up-votes.

  • 2

    If you think about it, there are more stack operations than other solutions. Each node will be pushed-popped-pushed-popped.

Log in to reply

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