Leet_Code/0144_binary_tree_pre_order_traversal.py at master · Kcheung42/Leet_Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#------------------------------------------------------------------------------
# Question: 0145_binary_tree_post_order_traversal.py
#------------------------------------------------------------------------------
# tags:
'''
Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,null,3]
   1
    \
     2
    /
   3

Output: [1,2,3]
'''

#------------------------------------------------------------------------------
# Solutions
#------------------------------------------------------------------------------
from typing import *
from test_utils.BinaryTree import TreeNode, BinaryTree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class SolutionRecur:
    '''
    Time: O(n)
    Space: O(1)
    '''
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        def recurUtil(root, result):
            if root is None:
                return
            result.append(root.val)
            recurUtil(root.left, result)
            recurUtil(root.right, result)

        result = []
        recurUtil(root, result)
        return result


class SolutionIter:
    '''
    Time: O(n)
    Space: O(n)
    '''
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        result = []
        while stack:
            root = stack.pop()
            result.append(root.val)
            if root.right is not None:
                stack.append(root.right)
            if root.left is not None:
                stack.append(root.left)
        return result


#------------------------------------------------------------------------------
# Tests
#------------------------------------------------------------------------------
import unittest

class TestSolution(unittest.TestCase):
    def test_simple(self):
        root = [1,None,2,None,None,3]
        root = BinaryTree(root).root

        s = SolutionRecur()
        self.assertEqual(s.preorderTraversal(root), [1,2,3])

        s = SolutionIter()
        self.assertEqual(s.preorderTraversal(root), [1,2,3])


unittest.main(verbosity=2)