3 python solutions(2 iteratively and 1 recursively), with explanation,easy understand


  • 0
    class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #recursively
        if not root:return []
        left,right=[],[]
        if root.left:
            left=self.postorderTraversal(root.left)
        if root.right:
            right=self.postorderTraversal(root.right)
        return left+right+[root.val]
        #iteratively-1
        stack,res=[],[]
        while stack or root:
            while root:
                stack.append((root,True)) #Travel the left child Tree
                root=root.left
            if stack:
                tmpNode,isFirst=stack.pop()  #isFirst whether the first time to travel this node, because we have to traval each node twice and the fist time,we can't vist the node, due to the right child tree needed to travel,but the second time, we could visit the node
                if isFirst:
                    stack.append((tmpNode,False))
                    root=tmpNode.right  #Travel the right child Tree
                else:
                    res.append(tmpNode.val)
                    root=None
        return res
        #iteratively-2
        if not root:return []
        stack,res=[root],[]
        pre=None
        while stack:
            cur=stack[-1]
            if (not cur.left and not cur.right) or (pre!=None and(pre==cur.right or pre==cur.left)):
                res.append(cur.val)
                stack.pop()
                pre=cur
            else:
                if cur.right:
                    stack.append(cur.right)
                if cur.left:
                    stack.append(cur.left)
        return res

Log in to reply
 

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