codility/binarywalk.py at master · jeff-chang/codility · GitHub

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
import random
class Node(object):
    def __init__(self, value=None):
        self.value = value
        self.depth = 0
        self.l = None
        self.r = None

class Tree(object):
    root = None
    depth = 0

    def add(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            newNode = Node(value)
            self._add(self.root, newNode)

    def _add(self, parentNode, newNode):
#        print parentNode.value, newNode.value
        if parentNode.value > newNode.value:
            self.depth = self.depth + 1
            if parentNode.l == None:
                 parentNode.l = newNode
#                 print "left"
#                 print parentNode.value, newNode.value
                 newNode.depth = self.depth
                 self.depth = 0
            else:
                 self._add(parentNode.l, newNode)
        else:
            self.depth = self.depth + 1
            if parentNode.r == None:
                 parentNode.r = newNode
#                 print "right"
#                 print parentNode.value, newNode.value
                 newNode.depth = self.depth
                 self.depth = 0
            else:
                 self._add(parentNode.r, newNode)

    def walk(self):
        if(self.root.value != None):
            self._walk(self.root)

    def _walk(self, node):
        if node.value != None:
            if node.l != None:
                self._walk(node.l)
            print str(node.value) + " " + str(node.depth)
            if node.r != None:
                self._walk(node.r)

    def path(self):
        self.path = []
        if(self.root.value != None):
           self._path(self.root)

    def _path(self, node):
        if node.value != None:
             self.path.append(node.value)
             if node.l == None and  node.r == None: #leaf
                 print self.path, self.diffDigits(self.path)
                 self.path.pop()
             else:
                 if node.l != None:
                     self._path(node.l)
                 if node.r != None:
                     self._path(node.r)
                 self.path.pop()

    def diffDigits(self, path):
        diffCount = 0
        for i in path:
            if diffCount < path.count(i):
                diffCount = path.count(i)
        return diffCount

def soultion(T):
    pass


Tree = Tree()
for i in range(50000):
    Tree.add(random.randint(0,50000))
# Tree.walk()
Tree.path()