Binary Tree Postorder Traversal LeetCode solution in Python

1
from typing import List, Optional
2

3

4
class Solution:
5
    """
6
    Time:   O(n)
7
    Memory: O(n)
8
    """
9

10
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
11
        if root is None:
12
            return []
13

14
        postorder = []
15
        stack = [root]
16

17
        while stack:
18
            node = stack.pop()
19
            postorder.append(node.val)
20
            if node.left is not None:
21
                stack.append(node.left)
22
            if node.right is not None:
23
                stack.append(node.right)
24

25
        return postorder[::-1]
26

27

28
class Solution:
29
    """
30
    Time:   O(n)
31
    Memory: O(n)
32
    """
33

34
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
35
        return list(self.postorder_generator(root))
36

37
    @classmethod
38
    def postorder_generator(cls, tree: Optional[TreeNode]):
39
        if tree is not None:
40
            yield from cls.postorder_generator(tree.left)
41
            yield from cls.postorder_generator(tree.right)
42
            yield tree.val