Skip to content

Commit 04442f8

Browse files
fritxfritx
committed
feat: add bintree-traversal
1 parent 96ff721 commit 04442f8

File tree

5 files changed

+180
-23
lines changed

5 files changed

+180
-23
lines changed

‎public/code/array-sort.py‎

Lines changed: 41 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,18 @@
1-
# 十大经典排序算法（python实现）（原创）
2-
# https://www.cnblogs.com/Mufasa/p/10527387.html
3-
41
sample = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 1, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
5-
sample_sorted = [1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
2+
sample_sorted = [1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5,
3+
6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
64

75
print(sample)
86
print(sample_sorted)
97

8+
109
def assert_list(actual, expected):
11-
len1 = len(actual)
12-
len2 = len(expected)
13-
if len1 == len2:
14-
for i in range(max(len1, len2)):
15-
if actual[i] != expected[i]: return actual
16-
return 'OK'
17-
return actual
10+
return 'OK' if actual == expected else actual
11+
12+
13+
# 十大经典排序算法（python实现）（原创）
14+
# https://www.cnblogs.com/Mufasa/p/10527387.html
15+
1816

1917
def bubble_sort(lst):
2018
while 1:
@@ -26,10 +24,12 @@ def bubble_sort(lst):
2624
if not touched: # 如果没有数值交换，那么就跳出
2725
break
2826

27+
2928
dt = sample[:]
3029
bubble_sort(dt)
3130
print('bubble_sort: ' + str(assert_list(dt, sample_sorted)))
3231

32+
3333
def selection_sort(lst):
3434
d1 = []
3535
while len(lst):
@@ -41,9 +41,11 @@ def selection_sort(lst):
4141
d1.append(min[1]) # 在新数组中添加
4242
return d1
4343

44+
4445
dt = selection_sort(sample[:])
4546
print('selection_sort: ' + str(assert_list(dt, sample_sorted)))
4647

48+
4749
def direct_insertion_sort(lst): # 直接插入排序，因为要用到后面的希尔排序，所以转成function
4850
d1 = [lst[0]]
4951
for i in lst[1:]:
@@ -57,10 +59,12 @@ def direct_insertion_sort(lst): # 直接插入排序，因为要用到后面
5759
d1.insert(0, i)
5860
return d1
5961

62+
6063
dt = direct_insertion_sort(sample[:])
6164
print('direct_insertion_sort: ' + str(assert_list(dt, sample_sorted)))
6265

63-
def binary_insertion_sort(lst): # 基于 direct_insertion_sort
66+
67+
def binary_insertion_sort(lst):
6468
d1 = [lst[0]]
6569
for i in lst[1:]:
6670
index_now = [-1, len(d1)]
@@ -78,9 +82,12 @@ def binary_insertion_sort(lst): # 基于 direct_insertion_sort
7882
index_now[1] = index
7983
return d1
8084

85+
8186
dt = binary_insertion_sort(sample[:])
8287
print('binary_insertion_sort: ' + str(assert_list(dt, sample_sorted)))
8388

89+
90+
# 基于 direct_insertion_sort
8491
def shell_sort(d): # d 为乱序数组，l为初始增量,其中l<len(d),取为len(d)/2比较好操作。最后还是直接省略length输入
8592
length = int(len(d) / 2) # 10
8693
num = int(len(d) / length) # 2
@@ -94,14 +101,15 @@ def shell_sort(d): # d 为乱序数组，l为初始增量,其中l<len(d),取为
94101
d[i + j * length] = d_mid[j]
95102
length = int(length / 2)
96103
if length == 0:
97-
return d
98104
break
99105
num = int(len(d) / length)
100106

107+
101108
dt = sample[:]
102109
shell_sort(dt)
103110
print('shell_sort: ' + str(assert_list(dt, sample_sorted)))
104111

112+
105113
def merge_sort(lst): # 分治发的典型应用，大问题拆分成小问题，逐个击破，之后将结果合并
106114
half_index = int(len(lst) / 2) # 将数组拆分
107115
d0 = lst[:half_index]
@@ -126,9 +134,11 @@ def merge_sort(lst): # 分治发的典型应用，大问题拆分成小问题
126134
break
127135
return d0
128136

137+
129138
dt = merge_sort(sample[:])
130139
print('merge_sort: ' + str(assert_list(dt, sample_sorted)))
131140

141+
132142
def quick_sort(lst):
133143
d = [[], [], []]
134144
d_pivot = lst[-1] # 因为是乱序数组，所以第几个都是可以的，理论上是一样的
@@ -140,7 +150,6 @@ def quick_sort(lst):
140150
else: # 等于基准值的放在中间
141151
d[1].append(i)
142152

143-
# print(d[0], d[1], d[2])
144153
if len(d[0]) > 1: # 大于基准值的子数组，递归
145154
d[0] = quick_sort(d[0])
146155
if len(d[2]) > 1: # 小于基准值的子数组，递归
@@ -150,16 +159,18 @@ def quick_sort(lst):
150159
d[0].extend(d[2])
151160
return d[0]
152161

162+
153163
dt = quick_sort(sample[:])
154164
print('quick_sort: ' + str(assert_list(dt, sample_sorted)))
155165

166+
156167
def counting_sort(lst):
157168
d_max = 0
158169
d_min = 0
159170
for i in lst:
160-
if d_max<i:
171+
if d_max < i:
161172
d_max = i
162-
if d_min>i:
173+
if d_min > i:
163174
d_min = i
164175

165176
d1 = {}
@@ -170,24 +181,26 @@ def counting_sort(lst):
170181
d1[i] = 1
171182

172183
d2 = []
173-
for i in range(d_min,d_max+1):
184+
for i in range(d_min, d_max+1):
174185
if i in d1.keys():
175186
for j in range(d1[i]):
176187
d2.append(i)
177188
return d2
178189

190+
179191
dt = counting_sort(sample[:])
180192
print('counting_sort: ' + str(assert_list(dt, sample_sorted)))
181193

194+
182195
def bucket_sort(lst):
183196
d1 = [[] for x in range(10)]
184197
for i in lst:
185-
d1[int(i/10)].append(i)
198+
d1[int(i / 10)].append(i)
186199
for i in range(len(d1)):
187200
if d1[i] != []:
188201
d2 = [[] for x in range(10)]
189202
for j in d1[i]:
190-
d2[j%10].append(j)
203+
d2[j % 10].append(j)
191204
d1[i] = d2
192205
d3 = []
193206
for i in d1:
@@ -199,12 +212,13 @@ def bucket_sort(lst):
199212
d3.append(k)
200213
return d3
201214

215+
202216
dt = bucket_sort(sample[:])
203217
print('bucket_sort: ' + str(assert_list(dt, sample_sorted)))
204218

219+
205220
def radix_sort(lst):
206221
d1 = [[] for x in range(10)]
207-
208222
# 第一次 最小位次排序
209223
for i in lst:
210224
d1[i % 10].append(i)
@@ -213,24 +227,26 @@ def radix_sort(lst):
213227
if i:
214228
for j in i:
215229
d0_1.append(j)
216-
217230
# 第二次 次低位排序
218231
d2 = [[] for x in range(10)]
219232
for i in d0_1:
220-
d2[int(i/10)].append(i)
233+
d2[int(i / 10)].append(i)
221234
d0_2 = []
222235
for i in d2:
223236
if i:
224237
for j in i:
225238
d0_2.append(j)
226239
return d0_2
227240

241+
228242
dt = radix_sort(sample[:])
229243
print('radix_sort: ' + str(assert_list(dt, sample_sorted)))
230244

245+
231246
# Python 堆排序 - 菜鸟教程
232247
# https://www.runoob.com/python3/python-heap-sort.html
233248

249+
234250
def heapify(arr, n, i):
235251
largest = i
236252
l = 2 * i + 1 # left = 2*i + 1
@@ -240,9 +256,10 @@ def heapify(arr, n, i):
240256
if r < n and arr[largest] < arr[r]:
241257
largest = r
242258
if largest != i:
243-
arr[i],arr[largest] = arr[largest],arr[i] # 交换
259+
arr[i], arr[largest] = arr[largest], arr[i] # 交换
244260
heapify(arr, n, largest)
245261

262+
246263
def heap_sort(arr):
247264
n = len(arr)
248265
# Build a maxheap.
@@ -253,6 +270,7 @@ def heap_sort(arr):
253270
arr[i], arr[0] = arr[0], arr[i] # 交换
254271
heapify(arr, i, 0)
255272

273+
256274
dt = sample[:]
257275
heap_sort(dt)
258276
print('heap_sort: ' + str(assert_list(dt, sample_sorted)))

‎public/code/async-exec-seq.csl.ts‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
// 浏览器与Node的事件循环(Event Loop)有何区别?
2+
// https://blog.csdn.net/Fundebug/article/details/86487117
3+
// 关于async/await、promise和setTimeout执行顺序
4+
// https://blog.csdn.net/yun_hou/article/details/88697954
5+
16
// 1.
27
console.log('---------- 1. ----------')
38
async function async1() {

‎public/code/bintree-traversal.py‎

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
# 144. 二叉树的前序遍历 - 145. 二叉树的后序遍历 - 94. 二叉树的中序遍历
2+
3+
class TreeNode:
4+
def __init__(self, x):
5+
self.val = x
6+
self.left = None
7+
self.right = None
8+
9+
10+
# 面试题07. 重建二叉树
11+
# https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/
12+
def buildTree(preorder, inorder):
13+
root, length, stack, index = TreeNode(preorder[0]), len(preorder), [], 0
14+
stack.append(root)
15+
for i in range(1, length):
16+
preorderval, node = preorder[i], stack[-1]
17+
if node.val != inorder[index]: # 每次比较栈顶元素和inorder[index]
18+
node.left = TreeNode(preorderval)
19+
stack.append(node.left)
20+
else:
21+
# 栈顶元素等于inorder[index],弹出；并且index += 1
22+
while stack and stack[-1].val == inorder[index]:
23+
node = stack[-1]
24+
stack.pop()
25+
index += 1
26+
node.right = TreeNode(preorderval)
27+
stack.append(node.right)
28+
return root
29+
30+
31+
preorder = [3, 9, 20, 15, 7]
32+
inorder = [9, 3, 15, 20, 7]
33+
print(str(["preorder", preorder]))
34+
print(str(["inorder", inorder]))
35+
root = buildTree(preorder, inorder)
36+
37+
38+
# 4. 前序-中序-后序 通用模板
39+
# https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/mo-fang-di-gui-zhi-bian-yi-xing-by-sonp/
40+
def preorderTraversal4(root):
41+
result, stack = [], [root]
42+
while stack:
43+
p = stack.pop()
44+
if p is None:
45+
p = stack.pop()
46+
result.append(p.val)
47+
else:
48+
# 先append的最后访问
49+
if p.right: # 1
50+
stack.append(p.right)
51+
if p.left: # 2
52+
stack.append(p.left)
53+
stack.append(p) # 3
54+
stack.append(None) # 3.1
55+
return result
56+
57+
58+
print(str(["Universal preorder", preorderTraversal4(root)]))
59+
60+
61+
# 3. 前序 - 莫里斯遍历
62+
# todo
63+
64+
65+
# 2. 后序 - 迭代
66+
# 执行用时: 16 ms , 在所有 Python 提交中击败了 88.59% 的用户
67+
# 内存消耗: 12.8 MB , 在所有 Python 提交中击败了 16.67% 的用户
68+
def postorderTraversal2(root):
69+
ans, stack = [], [root]
70+
while stack:
71+
node = stack.pop()
72+
if node:
73+
ans.append(node.val)
74+
if node.left:
75+
stack.append(node.left)
76+
if node.right:
77+
stack.append(node.right)
78+
return ans[::-1] # 逆序
79+
80+
81+
# 2. 中序 - 迭代
82+
# 执行用时: 12 ms , 在所有 Python 提交中击败了 98.00% 的用户
83+
# 内存消耗: 12.6 MB , 在所有 Python 提交中击败了 7.14% 的用户
84+
def inorderTraversal2(root):
85+
ans, stack, curr = [], [], root
86+
while curr or len(stack):
87+
while curr:
88+
stack.append(curr)
89+
curr = curr.left
90+
curr = stack.pop()
91+
ans.append(curr.val)
92+
curr = curr.right
93+
return ans
94+
95+
96+
# 2. 前序 - 迭代
97+
# 执行用时: 28 ms , 在所有 Python 提交中击败了 16.30% 的用户
98+
# 内存消耗: 13 MB , 在所有 Python 提交中击败了 5.56% 的用户
99+
def preorderTraversal2(root):
100+
ans, stack = [], [root]
101+
while stack:
102+
node = stack.pop()
103+
if node:
104+
ans.append(node.val)
105+
if node.right:
106+
stack.append(node.right)
107+
if node.left:
108+
stack.append(node.left)
109+
return ans
110+
111+
112+
print(str(["Iteration preorder", preorderTraversal2(root)]))
113+
print(str(["Iteration inorder", inorderTraversal2(root)]))
114+
print(str(["Iteration postorder", postorderTraversal2(root)]))
115+
116+
117+
# 1. 前序 - 递归
118+
# 执行用时: 20 ms , 在所有 Python 提交中击败了 69.51% 的用户
119+
# 内存消耗: 12.7 MB , 在所有 Python 提交中击败了 5.56% 的用户
120+
def preorderTraversal1(root):
121+
ans = []
122+
123+
def walk(node):
124+
if not node:
125+
return
126+
ans.append(node.val)
127+
walk(node.left)
128+
walk(node.right)
129+
walk(root)
130+
return ans
131+
132+
133+
print(str(["Recursion preorder", preorderTraversal1(root)]))

‎public/code/bintree-traversal.py.png‎

55.5 KB
Loading

‎public/code/index.yml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
- bintree-traversal.py
12
- array-sort.py
23
- nine-blocks.ts
34
- arr-func.csl.ts

0 commit comments

Comments
 (0)