Số nút lá trong cây con của mọi nút cây n-ary C++

Cho cây n-ary, tìm số nút lá cho mỗi cây con gốc tại từng nút.

Ví dụ: N=8, tree=[[2,3],[],[4,5,6],[7,8],[],[],[],[]] → 1->5, 2->1, 3->4, 4->2, 5->1, 6->1, 7->1, 8->1

Giải thuật

• DFS duyệt cây
• Mảng leaf[] lưu số lá của mỗi nút
• Mảng visited[]
• DFS(node): leaf[node]=0; visited=1; duyệt con chưa thăm: DFS(con); leaf[node] += leaf[con]; nếu không có con: leaf[node]=1
• In leaf[1..N]

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

void insertNode(int x, int y, vector<int> tree[]) { 
    tree[x].push_back(y); 
} 

void DFS(int node, int leaf[], int visited[], vector<int> tree[]) { 
    leaf[node] = 0; 
    visited[node] = 1; 
    for (auto it : tree[node]) { 
        if (!visited[it]) { 
            DFS(it, leaf, visited, tree); 
            leaf[node] += leaf[it]; 
        } 
    } 
    if (!tree[node].size()) { leaf[node] = 1; } 
} 

int main() { 
    int N = 8; 
    vector<int> tree[N + 1]; 
    insertNode(1, 2, tree); insertNode(1, 3, tree); 
    insertNode(3, 4, tree); insertNode(3, 5, tree); insertNode(3, 6, tree); 
    insertNode(4, 7, tree); insertNode(4, 8, tree); 
    int leaf[N + 1]; int visited[N + 1]; 
    for (int i = 0; i <= N; i++) visited[i] = 0; 
    DFS(1, leaf, visited, tree); 
    for (int i = 1; i <= N; i++) cout << i << "->" << leaf[i] << endl; 
    return 0; 
} 

Đầu ra

1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1