[LeetCode] 145. Binary Tree Postorder Traversal

Problem : https://leetcode.com/problems/binary-tree-postorder-traversal/

Recursive solution:

# 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]:
        
        def postorder(node):
            if node:
                yield from postorder(node.left)
                yield from postorder(node.right)
                yield node.val
        
        return list(postorder(root))

Iterative solution:

# 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]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack[-1]
            
            if not node.left and not node.right:
                result.append(node.val)
                stack.pop()
            else:
                if node.right:
                    stack.append(node.right)
                    node.right = None

                if node.left:
                    stack.append(node.left)
                    node.left = None

        return result

Edited on 04/20/2021. Add the recursive approach.

Edited on 04/20/2021. Update the stack based iterative approach.