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.
1const classifyNodes = (nodes) => {
2 const childCount = {};
3 const types = {};
4
5 nodes.forEach(([id, p_id]) => {
6 if (p_id !== null) {
7 if (!childCount[p_id]) childCount[p_id] = 0;
8 childCount[p_id]++;
9 }
10 types[id] = "Leaf";
11 });
12
13 nodes.forEach(([id, p_id]) => {
14 if (p_id === null) {
15 types[id] = "Root";
16 } else if (childCount[id]) {
17 types[id] = "Inner";
18 }
19 });
20
21 for (const id in types) {
22 console.log(id, types[id]);
23 }
24};
25
26const nodes = [[1, null], [2, 1], [3, 1], [4, 2], [5, 2]];
27classifyNodes(nodes);The JavaScript solution employs objects as dictionaries for managing child counts and node type assignments. After an initial scan to count children, nodes are confirmed as 'Root', 'Inner', or 'Leaf', which are printed in a console log for final output.
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.