Post Order Traversal - Following the same pattren as pre/Inorder


  • 0
    S

    Hello,

    General Rule for post order:
    Post order relies on if there exist a right node or not.
    If there is no right node, We have to add the current node to the result.
    If there is a right node, We have to do post order traversal on the right node.

    Once we traverse the right node and come back (stack.pop()) we need to know if we have already visited the node at which there exist a right node. For that reason I have used a boolean visited

    Postorder Iterative method:
    The algorithm goes like this:

    1. Visit the root node and go as left as you can
    2. Once you hit the end, Check if there exist a right node.
      2.1 No right node or Its already visited : Add the current node to the result
      2.2 Yes right node: Mark the current node to visited and make root = root.right, Repeat step 1
    3. Return the result.

    This way you are touching the nodes only once and there is no reverse of result at last.

    class Solution:
        def postorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            stack,result = [],[]
            while(root or len(stack) > 0):
                while(root):
                    stack.append((root,False))
                    root = root.left
                top,visited = stack.pop()
                if(top.right is None or visited is True):
                    result.append(top.val)
                else:
                    stack.append((top,True))
                    root = top.right
            return result
    

Log in to reply
 

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