java - 找到白色节点的最长路径

Question

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

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.

Answer 1

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

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

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