ツリー内で2番目に大きい値を見つける方法

Question

ツリー内で2番目に大きい要素を見つける方法の論理が得られません。

public static int largestR(TreeNode<Integer> root){ 
    if(root==null){ 
     return Integer.MIN_VALUE; 
    } 

    int max=root.data; 
    for(int i=0;i<root.children.size();i++){ 

     int n=largestR(root.children.get(i)); 
     if(max<n){ 
      max=n; 
     } 
    } 
    return max; 
} 

ツリーはバイナリではありませんノードは任意の数の子を持つことができます。

あなたは私にその解決策

感謝のコードのアルゴリズムを与えることができればそれは素晴らしいことです。

Answer 1

あなたはここでは代わりに1

の店舗2つの数字私の実装（構文が正しいことを確認していない）meed：さて、あなたは、ツリー内の最大値を取得する方法を知っています

public static void PushAnswer(int[] m, int value) 
{ 
    if (m[1] >= value) return; 
    if (m[0] >= value) 
    { 
     m[1] = value; 
     return; 
    } 

    m[1] = m[0]; 
    m[0] = value; 
} 

public static void largestR(TreeNode<Integer> root, int[] answer) 
{ 
    if (root == null) 
    { 
     return; 
    } 

    PushAnswer(answer, root.data); 
    for (int i = 0; i < root.children.size(); i++) 
    { 
     largestR(root.children.get(i)); 
    } 
} 

public static int[] getLargestR(TreeNode<Integer> root) 
{ 
    int[] answer = new int[2]; 
    answer[0] = Integer.MIN_VALUE; 
    answer[1] = Integer.MIN_VALUE; 
    largestR(root, answer); 

    return answer; 
} 

Answer 2

ここでは（あまり効率的ではありませんが、動作している）アルゴリズムです。あなたは、リストの中で最も高い要素を見つける方法を知っていると述べました。良い。その要素を削除します。最も高い要素を再度見つけてください！

代替：ソートアルゴリズムを使用してツリーをソートし、2番目の要素を取ります。

ただし、まだ効率が悪いです。最善の方法は、常に最大の2つの要素を追跡する独自のメソッドを作成することです。