1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_NODES 100
6
7typedef struct {
8    int id;
9    int p_id;
10} Node;
11
12typedef struct {
13    int id;
14    char type[10];
15} ResultNode;
16
17void classifyNodes(Node nodes[], int n, ResultNode result[]) {
18    int children[MAX_NODES] = {0};
19    int isRoot[MAX_NODES] = {0};
20
21    for (int i = 0; i < n; i++) {
22        if (nodes[i].p_id == -1) {
23            isRoot[nodes[i].id] = 1;
24            continue;
25        }
26        children[nodes[i].p_id]++;
27    }
28
29    for (int i = 0; i < n; i++) {
30        int id = nodes[i].id;
31        strcpy(result[i].type, "Leaf");
32        if (children[id] > 0) strcpy(result[i].type, "Inner");
33        if (isRoot[id]) strcpy(result[i].type, "Root");
34        result[i].id = id;
35    }
36}
37
38int main() {
39    Node nodes[] = {{1, -1}, {2, 1}, {3, 1}, {4, 2}, {5, 2}};
40    int n = 5;
41    ResultNode result[5];
42    classifyNodes(nodes, n, result);
43    for (int i = 0; i < n; i++) {
44        printf("%d %s\n", result[i].id, result[i].type);
45    }
46    return 0;
47}

1#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;
}