Given a binary tree, return the postorder traversal of its nodes' values.

Example:


Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]


Follow up: Recursive solution is trivial, could you do it iteratively?

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root==None:
             return []
         stack=[]
         stack_left=[1]
         while stack_left!=[]:
             stack.append(root.val)
             if root.left!=None and root.right==None:
                 root=root.left
             elif root.left==None and root.right!=None:
                 root=root.right
             elif root.left!=None and root.right!=None:
                 stack_left.append(root.left)
                 root=root.right
             else:
                 if stack_left==[1]:
                     stack_left=[]
                 else:
                     root=stack_left.pop()
         #print(stack)
         stack.reverse()
         return stack
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         ans = []
         if (root == None): return ans
         self.helper(root,ans)
         return ans
     
     def helper(self,root,ans):
         if (root == None):
             return
         self.helper(root.left,ans)
         self.helper(root.right,ans)
         ans.append(root.val)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         st, ans = [], []
         cur, last = root, None
         while cur or st:
             while cur:
                 st.append(cur)
                 cur = cur.left
             cur = st[-1]
             if not cur.right or cur.right == last:
                 ans.append(cur.val)
                 st.pop()
                 last = cur
                 cur = None
             else:
                 cur = cur.right
         return ans
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def __init__(self):
         self.l=[]
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root == None:
             return []
         self.postorderTraversal(root.left)
         self.postorderTraversal(root.right)
         self.l.append(root.val)
         return self.l

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         path = []
         
         def postOrder(root):
             if not root:
                 return
             postOrder(root.left)
             postOrder(root.right)
             path.append(root.val)
             
         postOrder(root)
         return path

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         trav = []
         self.post(root, trav)
         return trav
     
     def post(self, node, trav):
         if not node: return
         self.post(node.left, trav)
         self.post(node.right, trav)
         trav.append(node.val)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root == None:
             return []
         else:
             return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
         stack_left = [1]
         stack = []
         while stack_left:
             stack.append(root.val)
             if not root.left and root.right:
                 root = root.right
             elif root.left and not root.right:
                 root = root.left
             elif root.left and root.right:
                 stack_left.append(root.left)
                 root = root.right
             else:
                 if stack_left == [1]:
                     stack_left = []
                 else:
                     root = stack_left.pop()
         stack.reverse()
         return stack

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         self.post_traversal = []
         if root is None:
             return self.post_traversal
         self.postorderTraversals(root)
         return  self.post_traversal
 
     def postorderTraversals(self, root):
         if root.left:
             self.postorderTraversals(root.left)
         if root.right:
             self.postorderTraversals(root.right)
         self.post_traversal.append(root.val)
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         res = []
         self.dfs(root,res)
         return res
     
     def dfs(self,root,res):
         if root:
             self.dfs(root.left,res)
             self.dfs(root.right,res)
             res.append(root.val)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         res,stack=[],[(root,False)]
         while stack:
             node,flag=stack.pop()
             if node:
                 if flag:
                     res.append(node.val)
                 else:
                     stack.append((node,True))
                     stack.append((node.right,False))
                     stack.append((node.left,False))
         return res
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         res = []
         if not root:
             return res
         stack = []
         cur = root
         while cur or stack:
             while cur:
                 stack.append((cur, 0))
                 cur = cur.left
             node, flag = stack[-1]
             if flag:
                 node, _ = stack.pop()
                 res.append(node.val)
             else:
                 cur = node.right
                 stack[-1] = (node, 1)
         return res

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def postorderTraversal(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
 
         stack = [root]
         result = []
 
         while stack:
             node = stack.pop()
             if node.left or node.right:
                 stack.append(TreeNode(node.val))
                 if node.right:
                     stack.append(node.right)
                 if node.left:
                     stack.append(node.left)
             else:
                 result.append(node.val)
 
         return result