Iterative using stack 96.57%, Morris Iterative using O(1) space 100%, Recursive Summary


  • 0
    F
    1. Iterative using stack Beat 96.57%

    Basic idea is using preorder traversal but traverse right child node first, then left child node. Right->Left->Curr, then reverse the result

    class Solution(object):
        def postorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            stack, rst = [], []
            while stack or root:
                if root:
                    stack.append(root)
                    rst.append(root.val)
                    root = root.right
                else:
                    node = stack.pop()
                    root = node.left
            return rst[::-1]
    
    1. Morris Iterative Beat 100%
    class Solution(object):
        def postorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            #Morris traversal
            rst, curr = [], root
            while curr:
                if not curr.right:
                    rst.append(curr.val)
                    curr = curr.left
                else:
                    pre = curr.right
                    while pre.left and pre.left != curr:
                        pre = pre.left
                    if not pre.left:
                        pre.left = curr
                        rst.append(curr.val)
                        curr = curr.right
                        
                    else:
                        pre.left = None
                        curr = curr.left
            return rst[::-1]
    
    1. Recursive
    class Solution(object):
        def postorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            def helper(root):
                if not root: return
                helper(root.left)
                helper(root.right)
                rst.append(root.val)
            if not root: return []
            rst = []
            helper(root)
            return rst
    

    These three solutions can be applied to Inorder/Preorder traversal with very slightly modification.


  • 0
    A

    @Frog_pig For postorder traversal, using "reverse" is cheating. I know it works, but it is still cheating. You should think about how to respond when interviewers ask you not to use "reverse".


Log in to reply
 

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