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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7struct Node {
8 int id, p_id;
9};
10
11void classifyNodes(vector<Node>& nodes) {
12 unordered_map<int, int> childCount;
13 unordered_map<int, string> types;
14
15 for (const auto& node : nodes) {
16 if (node.p_id != -1) {
17 childCount[node.p_id]++;
18 }
19 types[node.id] = "Leaf";
20 }
21
22 for (const auto& node : nodes) {
23 if (node.p_id == -1) {
24 types[node.id] = "Root";
25 } else if (childCount[node.id]) {
26 types[node.id] = "Inner";
27 }
28 }
29
30 for (const auto& node : nodes) {
31 cout << node.id << " " << types[node.id] << endl;
32 }
33}
34
35int main() {
36 vector<Node> nodes = {{1, -1}, {2, 1}, {3, 1}, {4, 2}, {5, 2}};
37 classifyNodes(nodes);
38 return 0;
39}The C++ solution uses a vector to store the nodes and two unordered maps to record the child counts and types. By iterating over each node, we establish the type based on having children or being a root node, and print the results accordingly.
This approach centers around identifying nodes type by tracking parent relationships directly:
Steps:
Time Complexity: O(n)
Space Complexity: O(n)
In JavaScript, this approach with a Set ensures quick checks for whether a node acts as a parent, offering decisive breadth for type allocation alongside output agility.