Iterative method to do three kinds of traversal just like recursive method only changing one line code


  • 21

    For three different kinds of traversal, we only need to change the order of tuples in one line as we've done this in the recursive solution which is very decent and classical. Just put (0, p[1]) in different position!

    For post-order traversal:

    def postorderTraversal(self, root):
        res, stack = [], [(1, root)]
        while stack:
            p = stack.pop()
            if not p[1]: continue
            stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
        return res
    

    For in-order traversal:

    def inorderTraversal(self, root):
        res, stack = [], [(1, root)]
        while stack:
            p = stack.pop()
            if not p[1]: continue
            stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
        return res
    

    For pre-order traversal:

    def preorderTraversal(self, root):
        res, stack = [], [(1, root)]
        while stack:
            p = stack.pop()
            if not p[1]: continue
            stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)
        return res

  • 1

    Hah, nobody cares this solution... I think it's super easy to write when you face it in a interview. Just change the order in [(), (), ()]


  • 0
    Z

    @jedihy
    The solution is so elegant! Why nobody gives thumbs up for it.


  • 0
    P

    Excellent solution, have learned a lot from your post!!


  • 1
    D

    Can someone please rewrite this into c++? Not familiar with python... Thanks!


  • 0

    Here is my solution, using recursive + iterative + morris
    leetcode 145


  • 0
    W

    @jedihy could you explain a little about this code? thanks


Log in to reply
 

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