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）パスがツリー内で最長になります。ここでは証明しません。グーグルで証明するか、自分自身を証明してみてください（ただし、いくつかの例で実行すると、非常に明白です）。

解決策：
今あなたの問題。黒いノードは必要ないので、捨てましょう:)残りのグラフは森、つまり木のセットになります。既知のアルゴリズムを使用してすべてのツリーの最長パスを見つけ、すべての中から最長のパスを選択します。

複雑さ：
記述されたアルゴは、黒いノードを削除するために1つの線形パスを実行し、グラフ内のすべてのノードに対して線形であるフォレスト内のツリーごとに2つの線形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 に答える