0

我需要在树中找到最长的 ROOT 到 LEAF 路径。我已经有代码可以找到最短的根到叶子，我想知道我是否可以以任何方式重用它来找到最长的路径。

// Recursive function used by leftMostShortest
// to print the first shortest root to leaf path
void AlberoCircuito::printPath(string Data, unordered_map<string,
                             string> parent)
{
    // If the root's data is same as
    // its parent data then return
    if (parent[Data] == Data)
        return;

    // Recur for the function printPath
    printPath(parent[Data], parent);

    // Print the parent node's data
    pathMinimo.push_back(parent[Data]);
}


// Function to perform level order traversal
// until we find the first leaf node
vector<string> AlberoCircuito::leftMostShortest(NodoAlbero* root)
{
    // Queue to store the nodes
    queue<NodoAlbero*> q;

    // Push the root node
    q.push(root);

    // Initialize the value of first
    // leaf node to occur as -1
    string LeafData = " ";

    // To store the current node
    NodoAlbero* temp = NULL;

    // Map to store the parent node's data
    unordered_map<string, string> parent;

    // Parent of root data is set as it's
    // own value
    parent[root->value] = root->value;

    // We store first node of the smallest level
    while (!q.empty()) {
        temp = q.front();
        q.pop();

        // If the first leaf node has been found
        // set the flag variable as 1
        if (!temp->leftPtr && !temp->rightPtr) {
            LeafData = temp->value;
            break;
        }
        else {

            // If current node has left
            // child, push in the queue
            if (temp->leftPtr) {
                q.push(temp->leftPtr);

                // Set temp's left node's parent as temp
                parent[temp->leftPtr->value] = temp->value;
            }

            // If current node has right
            // child, push in the queue
            if (temp->rightPtr) {
                q.push(temp->rightPtr);

                // Set temp's right node's parent
                // as temp
                parent[temp->rightPtr->value] = temp->value;
            }
        }
    }

    // Recursive function to print the first
    // shortest root to leaf path
    printPath(LeafData, parent);

    // Print the leaf node of the first
    // shortest path
    pathMinimo.push_back(LeafData);
    return pathMinimo;
}

所以这是我用来查找最短路径并将其存储在向量中的代码。这些是一个类的成员。

有什么办法可以修改并重用它？还是你认为我必须重新开始？谢谢 ：）

4

0 回答 0