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.
1using System;
2using System.Collections.Generic;
3
4public class Node {
5 public int Id, PId;
6 public Node(int id, int pId) { Id = id; PId = pId; }
7}
8
9public class TreeNode {
10 public static void ClassifyNodes(List<Node> nodes) {
11 var childCount = new Dictionary<int, int>();
12 var types = new Dictionary<int, string>();
13
14 foreach (var node in nodes) {
15 if (node.PId != -1) {
16 if (!childCount.ContainsKey(node.PId)) childCount[node.PId] = 0;
17 childCount[node.PId]++;
18 }
19 types[node.Id] = "Leaf";
20 }
21
22 foreach (var node in nodes) {
23 if (node.PId == -1) {
24 types[node.Id] = "Root";
25 } else if (childCount.ContainsKey(node.Id)) {
26 types[node.Id] = "Inner";
27 }
28 }
29
30 foreach (var node in nodes) {
31 Console.WriteLine(node.Id + " " + types[node.Id]);
32 }
33 }
34
35 public static void Main() {
36 List<Node> nodes = new List<Node> {
37 new Node(1, -1), new Node(2, 1), new Node(3, 1), new Node(4, 2), new Node(5, 2)
38 };
39 ClassifyNodes(nodes);
40 }
41}The C# code utilizes a List collection for node storage and Dictionary collections for child counting and node type classification. This separation simplifies the program flow, with a focus on determining nodes statuses as 'Root', 'Inner', or 'Leaf', before printing the results.
This approach centers around identifying nodes type by tracking parent relationships directly:
Steps:
Time Complexity: O(n)
Space Complexity: O(n)
In this Java version, a HashSet allows quick lookup to determine if a node acts as a child elsewhere, helping to stratify node categories efficiently.