Độ sâu cây N-ary (N-Ary Tree Depth) trong C++

Cây N-ary (Multi-way Tree) là cây mà mỗi nút có thể có nhiều hơn 2 con (danh sách con). Độ sâu (Depth/Height) của cây là số lượng nút trên đường đi dài nhất từ gốc đến nút lá.

Cấu trúc nút

struct Node {
    char data;
    vector children; // Danh sách con động
    Node(char val) : data(val) {}
};

Phương pháp giải - Đệ quy DFS

depth(node) = 0 nếu node rỗng.
depth(node) = 1 + max(depth(child)) cho mọi con của node.

Chương trình C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    char data;
    vector children;
    Node(char val) : data(val) {}
};

int treeDepth(Node* root) {
    if (!root) return 0;
    int maxChildDepth = 0;
    for (Node* child : root->children) {
        maxChildDepth = max(maxChildDepth, treeDepth(child));
    }
    return 1 + maxChildDepth;
}

int main() {
    // Xây dựng cây: S -> O, A, D, N
    // O -> L, I
    // D -> R
    // N -> C, H, I
    Node* root = new Node('S');
    root->children = {new Node('O'), new Node('A'), new Node('D'), new Node('N')};
    root->children[0]->children = {new Node('L'), new Node('I')};
    root->children[2]->children = {new Node('R')};
    root->children[3]->children = {new Node('C'), new Node('H'), new Node('I')};
    
    cout << "Do sau cay N-ary: " << treeDepth(root) << endl;
    // Path dài nhất: S -> O -> L (hoặc I) -> Depth = 3? 
    // Wait: S(1) -> O(2) -> L(3). Depth = 3.
    // Code gốc output 2 (có thể đếm edge). Code này đếm node (depth=3).
    return 0;
}

Đầu ra

Do sau cay N-ary: 3

Lưu ý: Định nghĩa "Depth" đôi khi đếm số cạnh (edges) -> Kết quả = 2. Code trên đếm số nút (nodes) trên đường đi -> Kết quả = 3. Cần thống nhất định nghĩa.