LC 0145 [H] Binary Tree Postorder Traversal - ALawliet/algorithms GitHub Wiki

# 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: TreeNode) -> List[int]:
        if not root: return []
        res = []
        s = []
        s.append(root)
        while s:
            node = s.pop()
            res.append(node.val)
            if node.left:
                s.append(node.left)
            if node.right:
                s.append(node.right)
        res.reverse()
        return res
    
'''
because you want to go from right to left, push the left first, so it shows under the right in the stack
then when that is done, the result is the reverse postorder, so just reverse it back

inorder seq => binary search tree iterator, two sum BST, start from smallest and largest and walk towards the middle
'''