求以二叉树（左孩子右兄弟表示法）存储的N叉树的直径

核心思路 #

N叉树的直径定义为任意两个节点之间最长路径的边数，在左孩子右兄弟的二叉树存储结构中，每个节点的左孩子对应N叉树的第一个子节点，右兄弟对应N叉树的下一个同层级子节点。计算直径需要从三个维度考虑：

• 某一子节点子树内部的直径
• 两个不同子节点子树的最深路径，通过当前节点连接形成的路径
• 跨多层级的最长路径（通过递归向上传递结果）

递归过程中需要维护两个关键值：

1. 当前子树的最大深度：从当前节点到其最远子节点的边数
2. 当前子树的直径：当前子树内部的最长路径边数

具体步骤：

• 遍历当前节点的所有N叉树子节点（通过左孩子+右兄弟链表遍历）
• 对每个子节点递归计算其深度和直径，更新全局最大直径为所有子树直径的最大值
• 记录所有子节点子树的前两大深度，这两个深度之和即为通过当前节点连接的最长路径长度
• 当前子树的最大深度为「1 + 最大子节点深度」（当前节点到该子节点最远节点的路径）
• 当前子树的最终直径为「子树直径最大值」与「当前节点连接的最长路径」中的较大者

伪代码 #

首先定义节点结构：

struct Node {
    int val;
    Node* left;  // N叉树的第一个子节点
    Node* right; // N叉树的下一个兄弟节点
};

递归计算函数：

// 返回值：pair<当前子树最大深度, 当前子树直径>
pair<int, int> dfs(Node* node) {
    if (node == nullptr) {
        return {0, 0};
    }

    int max_sub_diameter = 0;
    int first_max_depth = 0, second_max_depth = 0;

    // 遍历当前节点的所有N叉树子节点
    Node* child = node->left;
    while (child != nullptr) {
        auto [child_depth, child_diameter] = dfs(child);
        
        // 更新子树中的最大直径
        if (child_diameter > max_sub_diameter) {
            max_sub_diameter = child_diameter;
        }

        // 更新前两大子节点深度
        if (child_depth > first_max_depth) {
            second_max_depth = first_max_depth;
            first_max_depth = child_depth;
        } else if (child_depth > second_max_depth) {
            second_max_depth = child_depth;
        }

        child = child->right;
    }

    // 当前子树的最大深度：当前节点到最远子节点的边数
    int current_max_depth = 1 + first_max_depth;
    // 当前节点能贡献的最长路径：两个最深子树路径之和
    int current_diameter = first_max_depth + second_max_depth;
    // 当前子树的最终直径取两者的较大值
    int final_diameter = max(max_sub_diameter, current_diameter);

    return {current_max_depth, final_diameter};
}

主调用函数：

int getNaryTreeDiameter(Node* root) {
    if (root == nullptr) return 0;
    auto [_, diameter] = dfs(root);
    return diameter;
}

对原有思路的说明 #

你之前仅统计左孩子数量的方法存在明显缺陷：它只计算了单一子节点链的长度，完全忽略了跨子节点的长路径（比如两个不同子树的最深节点通过父节点连接形成的路径），也没考虑子树内部的最长路径，因此无法得到正确的N叉树直径。

内容的提问来源于stack exchange，提问作者Cristea Tudor