-
Notifications
You must be signed in to change notification settings - Fork 0
/
consecutive_paths_NaryTree.py
74 lines (56 loc) · 1.74 KB
/
consecutive_paths_NaryTree.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
"""
Print all the consecutive paths in an N-ary tree. A path doesn't have to start
at root nor end at leaf, but its sequence has to be consecutive.
For example, 1 -> 2 -> 6 is not a consecutive path, but 1 -> 2 -> 3 is.
"""
import unittest
def find_consecutive_paths(root):
if root == None:
return
depth = get_depth(root)
path = [None] * depth
get_consecutive_paths(root, path, 0)
def get_consecutive_paths(node, path, level):
if node == None:
return
path[level] = node.data
for i in reversed(range(1, level + 1)):
if path[i] != path[i - 1] + 1:
break
else:
print_path(path, i - 1, level)
map(lambda x: get_consecutive_paths(x, path, level + 1), node.children)
def print_path(path, start, end):
for i in range(start, end + 1):
print path[i],
print "\n"
def get_depth(node):
if node == None:
return 0
elif not node.children:
return 1
else:
return 1 + max(list(map(lambda x: get_depth(x), node.children)))
class NaryTreeNode():
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, obj):
self.children.append(obj)
class TestConsecutivePaths(unittest.TestCase):
def test_1(self):
five = NaryTreeNode(5)
six = NaryTreeNode(6)
seven = NaryTreeNode(7)
one = NaryTreeNode(1)
two = NaryTreeNode(2)
seven2 = NaryTreeNode(7)
eight = NaryTreeNode(8)
three = NaryTreeNode(3)
five.children.extend([six, seven, one])
six.children.extend([two, seven2])
seven2.add_child(eight)
one.add_child(three)
find_consecutive_paths(five)
if __name__ == "__main__":
unittest.main()