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.
Solve with full IDE support and test cases
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)
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5struct Node {
6 int id, p_id;
7};
8
9void classifyNodes(const std::vector<Node>& nodes) {
10 std::unordered_set<int> isChild;
11
12 for (const auto& node : nodes) {
13 if (node.p_id != -1) {
14 isChild.insert(node.p_id);
15 }
16 }
17
18 for (const auto& node : nodes) {
19 if (node.p_id == -1) {
20 std::cout << node.id << " Root" << std::endl;
21 } else if (isChild.count(node.id)) {
22 std::cout << node.id << " Inner" << std::endl;
23 } else {
24 std::cout << node.id << " Leaf" << std::endl;
25 }
26 }
27}
28
29int main() {
30 std::vector<Node> nodes = {{1, -1}, {2, 1}, {3, 1}, {4, 2}, {5, 2}};
31 classifyNodes(nodes);
32 return 0;
33}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.