如何在C++非二叉树中查找最长路径并返回存储路径元素的vector

解决思路 #

你要找的多叉树最长路径本质是树的直径，实现核心逻辑是递归遍历每个节点，对每个节点做两件事：

• 收集所有子节点返回的「从子节点出发向下走的最长路径列表」，取长度最长的前两个，拼接当前节点后就是过当前节点的候选最长路径，和全局记录的最长路径比较更新
• 把当前节点拼在最长的子节点路径前面，作为当前节点返回的向下最长路径

实现代码 #

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

// 补全Name的类型定义，可根据你实际的Name类型调整
using Name = std::string;
struct Node
{
    std::string id;
    Name name;
    std::vector<Node*> children;
    Node* parent = nullptr;
};

std::unordered_map<std::string, Node> Node_data_;

// 递归函数：返回从当前节点向下延伸的最长路径节点列表，同时更新全局最长路径
std::vector<Node*> dfs(Node* cur, std::vector<Node*>& max_path) {
    std::vector<std::vector<Node*>> child_paths;
    for (Node* child : cur->children) {
        child_paths.push_back(dfs(child, max_path));
    }

    // 按子路径长度降序排序
    std::sort(child_paths.begin(), child_paths.end(), [](const std::vector<Node*>& a, const std::vector<Node*>& b) {
        return a.size() > b.size();
    });

    // 构造当前节点向下的最长路径
    std::vector<Node*> cur_longest;
    cur_longest.push_back(cur);
    if (!child_paths.empty()) {
        cur_longest.insert(cur_longest.end(), child_paths[0].begin(), child_paths[0].end());
    }

    // 构造过当前节点的候选最长路径
    std::vector<Node*> candidate;
    if (child_paths.size() >= 2) {
        std::reverse(child_paths[1].begin(), child_paths[1].end());
        candidate.insert(candidate.end(), child_paths[1].begin(), child_paths[1].end());
        candidate.push_back(cur);
        candidate.insert(candidate.end(), child_paths[0].begin(), child_paths[0].end());
    } else if (child_paths.size() == 1) {
        candidate = cur_longest;
    } else {
        candidate.push_back(cur);
    }

    // 更新全局最长路径
    if (candidate.size() > max_path.size()) {
        max_path = candidate;
    }

    return cur_longest;
}

// 对外调用接口，返回ID格式的最长路径列表
std::vector<std::string> get_longest_path() {
    // 查找根节点（parent为null的节点，如果你已知根节点可以直接赋值跳过这步）
    Node* root = nullptr;
    for (auto& entry : Node_data_) {
        if (entry.second.parent == nullptr) {
            root = &entry.second;
            break;
        }
    }
    if (!root) return {};

    std::vector<Node*> max_path;
    dfs(root, max_path);

    // 转换为ID列表，符合你需要的{A,B,D,I,L}格式
    std::vector<std::string> res;
    for (Node* node : max_path) {
        res.push_back(node->id);
    }
    return res;
}

注意事项 #

• 如果你的存储结构是多棵独立的树（森林），需要遍历所有根节点分别计算后取最长的路径
• 如果你需要返回Node对象列表而非ID列表，直接修改返回值类型和最后的转换逻辑即可
• 时间复杂度为O(n log k)，n为总节点数，k为单个节点的最大子节点数，常规业务场景性能足够

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