Sponsored
Sponsored
The idea is to identify the type of each node by examining the parent-child relationship. Specifically, to identify:
Steps:
Time Complexity: O(n), where n is the number of nodes, as we traverse through the list of nodes usually once or twice.
Space Complexity: O(n), used by the children count array and the result array.
1def classify_nodes(nodes):
2 child_count = dict()
3 types = dict()
4
5 for node in nodes:
6 id, p_id = node
7 if p_id != None:
8 child_count[p_id] = child_count.get(p_id, 0) + 1
9 types[id] = "Leaf"
10
11 for node in nodes:
12 id, p_id = node
13 if p_id is None:
14 types[id] = "Root"
15 elif id in child_count:
16 types[id] = "Inner"
17
18 for id in types:
19 print(id, types[id])
20
21nodes = [(1, None), (2, 1), (3, 1), (4, 2), (5, 2)]
22classify_nodes(nodes)The Python solution leverages dictionaries to count children and classify node types. By iterating over the list of nodes, it first initializes each node as a 'Leaf', then updates its status to 'Root' or 'Inner' based on its structural position in the tree.
This approach centers around identifying nodes type by tracking parent relationships directly:
Steps:
Time Complexity: O(n)
Space Complexity: O(n)
#include <vector>
#include <unordered_set>
struct Node {
int id, p_id;
};
void classifyNodes(const std::vector<Node>& nodes) {
std::unordered_set<int> isChild;
for (const auto& node : nodes) {
if (node.p_id != -1) {
isChild.insert(node.p_id);
}
}
for (const auto& node : nodes) {
if (node.p_id == -1) {
std::cout << node.id << " Root" << std::endl;
} else if (isChild.count(node.id)) {
std::cout << node.id << " Inner" << std::endl;
} else {
std::cout << node.id << " Leaf" << std::endl;
}
}
}
int main() {
std::vector<Node> nodes = {{1, -1}, {2, 1}, {3, 1}, {4, 2}, {5, 2}};
classifyNodes(nodes);
return 0;
}This C++ solution applies a hash set to identify if a node is a child, thus emphasizing the separation between 'Leaf' and 'Inner' nodes. It stands as an efficient resolution, particularly in observationally relating both parent and child logical controls.