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


  • 19
    G
    # 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:
                        result.append(cur.val)
                    else:
                        stack.append((cur.right, False))
                        stack.append((cur, True))
                        stack.append((cur.left, False))
    
            return result

  • 0
    P

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


  • 0
    1

    i like it ~ thank you~


  • 0
    E

    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
    K

    @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
    K

    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.