Binary Tree Inorder 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
11
        inorder = []
12
        stack = []
13

14
        while stack or root is not None:
15
            if root:
16
                stack.append(root)
17
                root = root.left
18
            else:
19
                node = stack.pop()
20
                inorder.append(node.val)
21
                root = node.right
22

23
        return inorder
24

25

26
class Solution:
27
    """
28
    Time:   O(n)
29
    Memory: O(n)
30
    """
31

32
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
33
        return list(self.inorder_generator(root))
34

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