Java recherche l'arbre entier pour la plus petite valeur

Question

Java recherche l'arbre entier pour la plus petite valeur

Ce n'est pas un arbre de recherche binaire, et ne suit aucune règle stricte.

Les seules règles sont que chaque nœud est un entier positif et que chaque nœud ne peut avoir aucun enfant, un enfant gauche ou deux enfants. (et pas seulement un droit de l'enfant).

Je veux traverser l'arbre entier en utilisant la récursivité et retourner la plus petite valeur que je trouve une fois terminé.

J'apprécierais que vous ne modifiiez pas la signature de la méthode ou n'utilisiez aucune méthode supplémentaire en dehors de Mathématique.min ()

public static int minValue(MyNode n) {
    int root, left, right;
    int min = -1;
    if (n.obj != null) {
        root = (int) n.obj;
        left = minValue(n.left);
        right = minValue(n.right);
        if (left < right)
            min = left;
        else
            min = right;
        if (root < min)
            min = root;
    }
    return min;
}

1

French java tree recursion binary-tree min

Author: Vadim Kotov, 2013-03-18

Source

1 answers

score 2 · Accepted Answer

Peut-être que le problème est que pour les enfants inexistants, vous retournez -1, mais plus tard, vous ne comptez pas avec cette possibilité. Vous devez supprimer -1 de l'analyse:

public static int minValue(MyNode n) {
    int root, left, right;
    int min = -1;
    if (n != null) {
        root = (int) n.obj;
        left = minValue(n.left);
        right = minValue(n.right);
        if (left > -1){
            if(right > -1){
                min = Math.min(left, right);
                min = Math.min(root, min);
            }
            else{
                min = Math.min(left, root);
            }
        }
        else{
            min = root;
        }
    }
    return min;
}