Binary Tree Preorder Traversal LeetCode solution in Python

1
# Runtime: 58 ms (Top 23.56%) | Memory: 13.9 MB (Top 60.28%)
2
from collections import deque
3
from typing import List, Optional
4

5

6
class Solution:
7
    """
8
    Time: O(n)
9
    Memory: O(n)
10
    """
11

12
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
13
        if root is None:
14
            return []
15

16
        queue = deque([root])
17
        preorder = []
18

19
        while queue:
20
            node = queue.pop()
21
            preorder.append(node.val)
22

23
            if node.right is not None:
24
                queue.append(node.right)
25
            if node.left is not None:
26
                queue.append(node.left)
27

28
        return preorder
29

30

31
class Solution:
32
    """
33
    Time: O(n)
34
    Memory: O(n)
35
    """
36

37
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
38
        return list(self.preorder_generator(root))
39

40
    @classmethod
41
    def preorder_generator(cls, tree: Optional[TreeNode]):
42
        if tree is not None:
43
            yield tree.val
44
            yield from cls.preorder_generator(tree.left)
45
            yield from cls.preorder_generator(tree.right)