Рубрики
Uncategorized

Проблема с кодом кода PHP–D96 530. Минимальная абсолютная разница в ЛУЧШЕМ

Автор оригинала: David Wong.

Ссылки на Темы

530. Минимальная абсолютная разница в BST

Анализ темы

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

размышляющий

Сначала получают все значения узлов, а затем сравнивают их одно за другим. Но это неэффективно.

Окончательный код

php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    protected $values = [];

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function getMinimumDifference($root) {
        $this->preOrder($root);
        $amount = count($this->values);
        $minValue = 9999999;
        for($i=0; $i<$amount; $i++){
            for($j=$i+1;$j<$amount; $j++){
                $diff = abs($this->values[$i] - $this->values[$j]);
                if($diff<$minValue){
                    $minValue = $diff;
                }
            }
        }
        return $minValue;
    }
    
    function preOrder($root){
        if(is_null($root->val)){
           return; 
        }
        $this->values[] = $root->val;
        if($root->left){
            $this->preOrder($root->left);
        }
        if($root->right){
            $this->preOrder($root->right);
        }
    }
    
}

Если вы считаете, что эта статья полезна для вас, вы можете воспользоваться Фондом генерации энергии Ии.