Наименьшая абсолютная разница бинарного дерева поиска вручную

внешний интерфейс алгоритм
Наименьшая абсолютная разница бинарного дерева поиска вручную

Это 27-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления

Всем привет, сегодня 27-й день моего участия в августовском обновлении.Алгоритмическая задача, связанная с бинарными деревьями, принесенная вам сегодня, это минимальная абсолютная разность бинарных деревьев поиска.Текст следующий:

тема

Учитывая бинарное дерево поиска, узлы которого неотрицательны, рассчитайте минимальное значение абсолютного значения разницы между любыми двумя узлами в дереве.

Пример:

输入：

   1
    \
     3
    /
   2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

Идеи решения проблем

По смыслу вопроса бинарное дерево - это бинарное дерево поиска, поэтому мы можем использовать обход по порядку для обхода всего бинарного дерева, и мы получим упорядоченный массив, а затем пройдемся по массиву и пройдемся по массиву. в свою очередь, значение , чтобы получить минимальную абсолютную разность;

Приведенное выше решение является допустимым решением. Кроме того, мы также можем использовать метод поиска при обходе, чтобы получить минимальную абсолютную разницу. Конкретные идеи заключаются в следующем:

  1. Определите глобальную переменную для записи минимальной абсолютной разницы и определите глобальную переменную для записи предыдущего значения обхода двоичного дерева;
  2. Если узел имеет значение null, он вернется напрямую;
  3. В порядке обхода бинарного дерева, если pre = -1, это означает, что узел является корневым узлом, и присвоить значение корневого узла pre, в противном случае вычислить абсолютное значение разницы между текущим узлом и предыдущий узел, и сравнить его с ans, принять Минимальное значение присваивается ans;

Код

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans;
    int pre;
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        inOrder(root);
        return ans;
    }

    public void inOrder(TreeNode node){
        if (node == null) {
            return;
        }
        inOrder(node.left);
        if (pre == -1) {
            pre = node.val;
        } else {
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
        }
        inOrder(node.right);
    }
}

наконец

Анализ сложности:

  • Временная сложность: O(n), где n — количество узлов бинарного дерева поиска. Каждый узел посещается один раз и только один раз при обходе по порядку, поэтому общая временная сложность составляет O (n).

  • Пространственная сложность: O(n). Пространственная сложность рекурсивной функции зависит от глубины рекурсивного стека, которая может достигать уровня O(n), когда бинарное дерево поиска представляет собой цепочку.

Категории