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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
class Node:
def __init__(self, val, left=None, right=None) -> None:
self.val = val
self.left = left
self.right = right
def create_tree(data: list):
if not data:
return None
first_node = Node(data[0])
tmp_list = [first_node]
tmp_count = 0
for item in data[1:]:
node = tmp_list[0]
new_node = Node(item) if item is not None else None
if tmp_count == 0:
node.left = new_node
# add to tmp_list
if item is not None:
tmp_list.append(new_node)
tmp_count += 1
continue
if tmp_count == 1:
node.right = new_node
if item is not None:
tmp_list.append(new_node)
# POP
tmp_list.pop(0)
tmp_count = 0
continue
return first_node
def pre_order_traversal(tree: Node):
ret = []
def innner(node):
if node is None:
return
ret.append(node.val)
innner(node.left)
innner(node.right)
innner(tree)
return ret
def in_order_traversal_with_loop(tree: Node):
ret = []
# stack
tmp_list = [tree]
passed_node = []
while True:
if not tmp_list:
break
node = tmp_list[-1]
if node.left is not None and node not in passed_node:
passed_node.append(node)
tmp_list.append(node.left)
continue
# 出
node = tmp_list.pop()
ret.append(node.val)
if node.right is not None:
# 压
tmp_list.append(node.right)
return ret
def in_order_traversal(tree: Node):
ret = []
def innner(node):
if node is None:
return
innner(node.left)
ret.append(node.val)
innner(node.right)
innner(tree)
return ret
def post_order_traversal(tree: Node):
ret = []
def innner(node):
if node is None:
return
innner(node.left)
innner(node.right)
ret.append(node.val)
innner(tree)
return ret
if __name__ == '__main__':
data = list(range(10))
tree = create_tree(data)
print(tree)
print(pre_order_traversal(tree))
print(in_order_traversal(tree))
print(pre_order_traversal_with_loop(tree))
# 0
# 1 2
# 3 4 5 6
# 7 8 9
|