Как найти второе по величине значение в дереве

Question

Я не получаю логику того, как найти второй по величине элемент в дереве.

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

Вы MEED магазин 2 номера вместо 1.

Вот моя реализация (не уверен, что синтаксис правильный):

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

Вот (не очень эффективный, но рабочий) алгоритм. Вы заявили, что знаете, как найти наивысший элемент в списке. Хорошо. Удалите этот элемент. Найти наивысший элемент снова!

Альтернативно: Сортируйте дерево, используя алгоритм сортировки и возьмите второй элемент.

Все еще неэффективен. Лучше всего написать свой собственный метод, который всегда отслеживает два самых больших элемента.