From cefc6a2cd763e09adb8b4df33697df4a2cb5ddab Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Thu, 10 Jan 2019 20:36:29 -0600 Subject: Tree height done! Fun exercise. Interesting to experience the mentality change of creating classes in Python, after first creating it in Java. I removed the parent property in Python class since it's not used. Object aliasing caused a bug that took me a bit to figure out. --- sources/tree_height.py | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 71 insertions(+) create mode 100644 sources/tree_height.py (limited to 'sources') diff --git a/sources/tree_height.py b/sources/tree_height.py new file mode 100644 index 0000000..9cebe3a --- /dev/null +++ b/sources/tree_height.py @@ -0,0 +1,71 @@ +# Uses python3 +import queue + + +class Node(object): + def __init__(self, key): + self._key = key + self.children = [] + + @property + def key(self): + return self._key + + @key.setter + def key(self, key): + self._key = key + + def add_child(self, child): + self.children.extend([child]) + + def get_children(self): + return self.children + + +def tree_level_counter(nodes, root_index): + level_counter = 1 + q = queue.Queue() + pop_count = 0 + child_count = len(nodes[root_index].get_children()) + grand_children_count = 0 + for i in range(child_count): + q.put(nodes[root_index].get_children()[i]) + while not q.empty(): + if pop_count < child_count: + node = q.get() + i = len(node.get_children()) + if i != 0: + for j in range(i): + q.put(node.get_children()[j]) + grand_children_count = grand_children_count + i + pop_count = pop_count + 1 + else: + pop_count = 0 + child_count = grand_children_count + grand_children_count = 0 + level_counter = level_counter + 1 + return level_counter + 1 + + +def get_height(a): + # The code below has the bug of alias/referencing. Code after that fixed it. + # nodes = [Node(-5)] * len(a) + nodes = [] + for i in range(len(a)): + nodes.append(Node(i)) + root_index = 0 + + for i in range(len(a)): + parent_index = a[i] + nodes[i].key = i + if parent_index == -1: + root_index = i + else: + nodes[parent_index].add_child(nodes[i]) + return tree_level_counter(nodes, root_index) + + +if __name__ == '__main__': + n = int(input()) + parents = list(map(int, input().split())) + print(get_height(parents)) -- cgit v1.2.3