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
| # 前序遍历递归
def pre_order(root, result):
if root is None:
return result
result.append(root.data)
pre_order(root.left, result)
pre_order(root.right, result)
return result
# 前序非递归
def pre_order(root, result):
stack = [root]
while len(stack) > 0:
result.append(root.val)
if root.right is not None:
stack.append(node.right)
if root.left is not None:
stack.append(node.left)
root = stack.pop()
return result
# 中序遍历递归
def mid_order(root, result):
if root is None:
return result
pre_order(root.left, result)
result.append(root.data)
pre_order(root.right, result)
return result
# 中序遍历非递归
def mid_order(root, result):
stack = []
node = root
while node is not None or len(stack) > 0:
if node is not None:
stack.append(node)
node = node.left
else:
node = stack.pop()
result.append(node.val)
node = node.right
return result
# 后序遍历递归
def back_order(root, result):
if root is None:
return result
pre_order(root.left, result)
pre_order(root.right, result)
result.append(root.data)
return result
# 后序遍历非递归
def back_order(root, result)
stack = [root]
stack2 = []
while len(stack) > 0:
node = stack.pop()
stack2.append(node)
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
while len(stack2) > 0:
result.append(stack2.pop().val)
return result
# 按层遍历
def layer_traverse(root, result):
if not root:
return result
que = queue.Queue()
que.put(root)
while not qye.empty():
root = que.get()
result.append(root)
if root.left:
que.put(root.left)
if root.right:
que.put(root.right)
|
