Binary Tree: Postorder Traversal

# Definition for a binary tree node.
from typing import List

class TreeNode:
    def __init__(self, x: int) -> None:
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]:
        """
                    0
                 /     \    
                1        2
              /   \
            3       4
                  /   \
                6       9

        Post-order...: [3, 6, 9, 4, 1, 2, 0]

        T: O(N)
        S: O(N) worst case; O(log N) average
        """
        
        if result is None:
            result = []

        if not root:
            return []
        
        self.traversal(root.left, result=result)
        self.traversal(root.right, result=result)
        result.append(root.val)

        return result

from collections import deque
class Solution:
    def traversal(self, root: 'TreeNode')->List[List[int]]:
        """
                    0
                 /     \    
                1        2
              /   \
            3       4
                  /   \
                6       9

        Post-order...: [3, 6, 9, 4, 1, 2, 0]

        T: O(N)
        S: O(N)
        """

        if not root:
            return []

        stack = [(root, False)]
        result = []

        while stack:
            node, visited = stack.pop()
            
            if node:
                if visited:
                    result.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
        
        return result