2

在一次采访中提出了这个问题：给出了具有黑白节点的树。在给定的树中找到最长的白色节点路径。下面的方法是否正确或有人帮助提供更好的方法谢谢！

int Longest(node root, int max)
{
    if(root==null || root.color == black)
        return 0;
    if(root.color == white)
    {

      int curmax =1+ firstlongest(root.child) + secondlongest(root.child); 

        if(curmax>max) 
            max = curmax;
        return curmax;
    }
    if(root.color == black)
    {
        for(all children)
        {
            int curmax =1+ firstlongest(root.child) + secondlongest(root.child); 
        }
        if(curmax>max) 
            max =curmax;
        return 0;
    }
}

 int firstlongest(node* child){//will calculate first longest of children and similarly 
 secondlongest gives second.Finally max will have length of longest path.
4

3 回答 3

3

简介：
首先记住如何在树中找到最长的路径。你取一个任意顶点v，用 bfs 找到离它最远的顶点u，然后再用 bfs 找到离u最远的顶点t，并且(u,t)路径将是树中最长的。我不会在这里证明它，您可以搜索它或尝试证明自己（不过，如果您在一些示例上运行它，这很明显）。

解决方案：
现在你的问题。我们不需要黑色节点，所以让我们把它们扔掉吧:) 剩下的图将是一个森林，即一组树。用已知算法为每棵树找到最长的路径，并在所有路径中选择最长的。

复杂性：
描述的算法将执行一次线性传递以删除黑色节点，并为森林中的每棵树执行两个线性 bfs，这对图中的所有节点都是线性的。总共：O(n) + O(n+m) + O(n+m) = O(n+m)

于 2013-02-13T08:57:30.750 回答
2

代码对我来说似乎不正确。以下部分：

if(root.color == black)
{
    for(all children)
    {
        int curmax = max(longest(root.child[i], max));
    }
    if(curmax>max) 
        max =curmax;
    return 0;
}

永远不会被执行，因为 ifroot.color == black方法会提前返回 0。

这是我将如何做到这一点：

private static int longestWhitePathFromRootLength (Node node)
{
    if (node.color == BLACK)
        return 0;
    else // node.color == WHITE
    {
        int l = 0;

        for (Node n: node.children)
        {
            l = Math.max (l, longestWhitePathFromRootLength (n));
        }

        return l + 1;
    }
}

public static int longestWhitePathLength (Node node)
{
    int l = 0;

    for (Node n: node.children)
    {
        l = Math.max (l, longestWhitePathLength (n));
    }

    return Math.max (l, longestWhitePathFromRootLength (node));
}
于 2013-02-13T08:31:32.940 回答
2

您的程序似乎只计算下降的路径。假设所有节点都是白色的，它将错过这棵树中最长的路径：

      r
     /
    a
   / \
  b   c
 /     \
d       e

最长的路径是dbace。

于 2013-02-13T08:36:47.467 回答