Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

👨‍💻 Алгоритм:

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    private $inorderNodes = [];
    
    private function inorderTraversal($root) {
        if ($root === null) {
            return;
        }
        
        $this->inorderTraversal($root->left);
        $this->inorderNodes[] = $root->val;
        $this->inorderTraversal($root->right);
    }
    
    public function minDiffInBST($root) {
        $this->inorderTraversal($root);
        
        $minDistance = PHP_INT_MAX;
        for ($i = 1; $i < count($this->inorderNodes); $i++) {
            $minDistance = min($minDistance, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
        }
        
        return $minDistance;
    }
}

Ставь 👍 и забирай 📚 Базу знаний