-
Notifications
You must be signed in to change notification settings - Fork 319
/
ch-1.py
executable file
·54 lines (47 loc) · 965 Bytes
/
ch-1.py
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
#! /usr/bin/python3
import unittest
def str2tree(str):
o=[0]
d=0
p=0
for e in str.split():
if e == '|':
d += 1
p=0
m=(1<<(d+1))-1
while len(o) < m:
o.append(0)
else:
if e == '*':
y=0
else:
y=int(e)
i = (1<<d) - 1 + p
o[i]=y
p += 1
return o
def mindepth(tree):
firstleaf=len(tree)
for i,e in enumerate(tree):
if e==0:
continue
elif (i+1) << 1 >= len(tree):
firstleaf=i
break
else:
ni=((i+1) << 1) -1
if tree[ni]==0 and tree[ni+1]==0:
firstleaf=i
break
t=firstleaf+1
d=0
while t > 0:
t >>= 1
d += 1
return d
class TestStr2tree(unittest.TestCase):
def test_ex1(self):
self.assertEqual(mindepth(str2tree("1 | 2 3 | 4 5")),2,'example 1')
def test_ex2(self):
self.assertEqual(mindepth(str2tree("1 | 2 3 | 4 * * 5 | * 6")),3,'example 2')
unittest.main()