Nun soll die Anzahl der Knoten in einem binären Baum gezählt werden. Die Klasse Node…
- User
Nun soll die Anzahl der Knoten in einem binären Baum gezählt werden. Die Klasse Node sieht wie folgt aus:
class Node: def init(self): self.parent = None self.left = None self.right = None
Der Algorithmus sollte eine Laufzeit von O(n) haben (n ist die Anzahl der Knoten im Baum).
Eingabe: Die Wurzel des binären Baums. Die Anzahl der Knoten im Baum ist zwischen 1 und 1000.
Ausgabe: Die Anzahl der Knoten im Baum.
- Assistant
class Node: def init(self): self.parent = None self.left = None self.right = None
def count(self): c = 0 # count all inner nodes if self.left: c = self.left.count() if self.right: c += self.right.count() # the current count needs also be counted c += 1 return c - User
Ich würde gerne eine nicht rekursive Lösung haben.
- Assistant
Eine nicht rekursive Lösung, die eine Laufzeit von O(n) hat, wäre wie folgendes:
def count_nodes(node): count = 0 nodes_to_search = [node]
while len(nodes_to_search) > 0: count += len(nodes_to_search) new_nodes = [] for node_to_search in nodes_to_search: if node_to_search.left is not None: new_nodes.append(node_to_search.left) if node_to_search.right is not None: new_nodes.append(node_to_search.right) nodes_to_search = new_nodes
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →
- Human-written demonstration (OpenAssistant volunteers)Compare side by side →