a = input() class Node(): def __init__(self, value, depth=0): self.value = value self.left = self.right = None self.depth = depth def insert(self, value): if value <= self.value: if self.left == None: self.left = Node(value, self.depth+1) # print(f'{value} is the left child of {self.value}') else: self.left.insert(value) if value > self.value: if self.right == None: self.right = Node(value, self.depth+1) # print(f'{value} is the right child of {self.value}') else: self.right.insert(value) def children(self): children = 0 if self.left != None: children += 1 if self.right != None: children += 1 return children def match(self, other): if self.left == None and self.right == None: return True if other.left == None and self.left != None: return False if other.right == None and self.right != None: return False if self.left == None: return self.right.match(other.right) if self.right == None: return self.left.match(other.left) return self.left.match(other.left) and self.right.match(other.right) def traverse(self): # print(self.value, self.left, self.right) yield self if self.left != None: yield from self.left.traverse() if self.right != None: yield from self.right.traverse() A = Node(a[0]) for c in a[1:]: A.insert(c) leaf = external = external_path = internal_path = depth = 0 for node in A.traverse(): if node.children() == 0: leaf += 1 external += 2 external_path += 2*(node.depth+1) if node.children() == 1: external += 1 external_path += node.depth+1 internal_path += node.depth depth = max(node.depth, depth) print(depth, leaf, external, internal_path, external_path)
a = input() class Node(): def __init__(self, value, depth=0): self.value = value self.left = self.right = None self.depth = depth def insert(self, value): if value <= self.value: if self.left == None: self.left = Node(value, self.depth+1) # print(f'{value} is the left child of {self.value}') else: self.left.insert(value) if value > self.value: if self.right == None: self.right = Node(value, self.depth+1) # print(f'{value} is the right child of {self.value}') else: self.right.insert(value) def children(self): children = 0 if self.left != None: children += 1 if self.right != None: children += 1 return children def match(self, other): if self.left == None and self.right == None: return True if other.left == None and self.left != None: return False if other.right == None and self.right != None: return False if self.left == None: return self.right.match(other.right) if self.right == None: return self.left.match(other.left) return self.left.match(other.left) and self.right.match(other.right) def traverse(self): # print(self.value, self.left, self.right) yield self if self.left != None: yield from self.left.traverse() if self.right != None: yield from self.right.traverse() A = Node(a[0]) for c in a[1:]: A.insert(c) leaf = external = external_path = internal_path = depth = 0 for node in A.traverse(): if node.children() == 0: leaf += 1 external += 2 external_path += 2*(node.depth+1) if node.children() == 1: external += 1 external_path += node.depth+1 internal_path += node.depth depth = max(node.depth, depth) print(depth, leaf, external, internal_path, external_path)2. E
3. A
12. B
1. E
2. A
3. B