Нахождение мин в бинарном дереве? - PullRequest
Новая
       10

Нахождение мин в бинарном дереве?

0 голосов
/ 08 марта 2020

Я пытаюсь найти мин для бинарного дерева, а не бинарного дерева поиска, но не могу получить ответ, код ниже. Пожалуйста, скажите мне, что не так. Изменить: Таким образом, с помощью плаката, я смог заставить работать код. Я заставил код 1 работать, но я не понимаю, почему в коде 2 нам нужно снова проверять Math.min, когда в коде 1 нам не нужно было это делать.

Код 1: 

    static int min = 0;
    static public int findMinimumValue(Node root) {
       min = root.data;
           findMinimumValue(root, root.data);
           return min;
   }
      static public int findMinimumValue(Node root, int x) {

          if(root == null) {
                return min;
            } else {
                if(root.data < min) {

                    min = root.data;
                }
                int left = findMinimumValue(root.left, x);
                int right = findMinimumValue(root.right, x);
               return min;

            }
        }

Код 2: 


   static public int findSecondMinimumValue(Node root) {
      // min = root.data;
        return findSecondMinimumValue(root, root.data);
 }
    static public int findSecondMinimumValue(Node root, int min) {

        if(root == null) {
              return min;
          } else {
              if(root.data < min) {

                  min = root.data;
              }
              int left = findSecondMinimumValue(root.left, min);
              int right = findSecondMinimumValue(root.right, min);


            return Math.min(left, right);
          }
      }

1 Ответ

2 голосов
/ 08 марта 2020

Шаг 1. Определите проблему

Выполните все, что вы сделали в базе кода. Давайте создадим двоичное дерево: 

      5
    /  \
   2    1

Очевидно, что минимум равен 1, верно? Итак, следуйте вашему коду с этим примером. 

public int findMinimumValue(TreeNode root) {
    return findMinimumValue(root, root.val);
}

root будет отправной точкой. 

        int left = findMinimumValue(root.left, min);
        int right = findMinimumValue(root.right, min);

Это то, что будет видеть каждый узел (если он не является нулевым). Это рекурсивный вызов влево, затем вправо после того, как он прошел как можно левее.

finalMinimumValue (TreeNode (5), 5)

Вызывает следующее: 

int left = finalMinimumValue(TreeNode(2), 5);
int right = finalMinimumValue(TreeNode(1), 5)

finalMinimumValue (TreeNode (2), 5)

Вызывает следующее: 

int left = finalMinimumValue(null, 5);
int right = finalMinimumValue(null, 5)

finalMinimumValue (null, 5)

Имеет ли следующий код : 

return min;

Что такое мин ? мин, ну, 5.

Это имеет смысл? Мы прошли через 2, но все еще сохранили мин. Как 5.

Шаг 2. Устраните проблему

На шаге 1 мы пришли к выводу, что для нас нет смысла не обновлять min, если мы в настоящее время на узле, который не является минимальным. Итак, давайте обновим его до , мы также рекурсивно go вниз. 

public int findMinimumValue(TreeNode root) {
    return findMinimumValue(root, root.val);
}

public int findMinimumValue(TreeNode root, int min) {

    if (root == null) {
        return min;
    } else {
        // update your min variable here by comparing it with the node you currently are at!

        int left = findMinimumValue(root.left, min);
        int right = findMinimumValue(root.right, min);
        if (left < min) {
            min = left;
        }
        if (right < min) {
            min = right;
        }
        return min;
    }
}

Шаг 3. Протестируйте решение

Давайте рассмотрим тот же пример. Мы ожидаем, что он скажет, что он равен 1. 

      5
    /  \
   2    1

1: вычисление осталось для узла root

Значение нашего узла равно 5. На 5 меньше значения нашего узла (5 )? Итак, не обновляйте мин.

Далее, вызовите левого потомка, Node (2)

2: вычислите мин, чтобы вернуться для узла 2

Значение нашего узла равно 2. Является ли значение 5 меньше значения нашего узла (2)? Да! Итак, обновите наше минимальное значение.

Теперь min равно 2.

Далее, вызовите левого потомка, null . Поскольку его левый потомок равен нулю, мы возвращаем min, что равно 2.

Теперь вызовем правого потомка, null . Так как его правый дочерний элемент равен нулю, мы возвращаем min, что равно 2.

Ну, левый равен 2, правый равен 2. Итак, вернем 2!

3: вычисляем min для возврата для Узел 1

Значение нашего узла равно 1. Является ли значение 5 меньше значения нашего узла (1)? Да! Поэтому обновите мин.

Теперь минимальное значение равно 1.

Далее, вызовите левого потомка, null . Так как его левый потомок равен нулю, мы возвращаем min, что равно 1.

Теперь, вызовем правого потомка, null . Так как его правый дочерний элемент равен нулю, мы возвращаем min, равное 1.

Ну, левый равен 1, правый равен 1. Итак, возвращаем 1!

4: вычисляем min для возврата для узел root.

Левые вернули нас 2. Правые вернули нам 1.

Поскольку 1 меньше 2, 1 - это ответ.

Это работает !

...