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

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.

• @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".

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