Проблема с PHP-кодом Leetcode — D89 653. Две суммы IV

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

653. Две суммы IV – Вход-это BST

Анализ темы

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

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

Мысль 1

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

Этот алгоритм явно неэффективен.

Идея 2

При обходе сохраняйте себя как ключ в массиве. Функция isset используется для определения того, находится ли разница между числом и числом в массиве. Существование возвращается. В противном случае пройдите по дочерним узлам.

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

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 $has = [];
    protected $hasResult = false;
    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Boolean
     */
    function findTarget($root, $k) {
        if(is_null($root)){
            return;
        }
        if(isset($this->has[$k-($root->val)])){
            $this->hasResult = true;
            return $this->hasResult;
        }
        else{
            $this->has[$root->val] = true;
            if(!$this->findTarget($root->left, $k)){
                $this->findTarget($root->right, $k);
            }
        }
        return $this->hasResult;
    }
}

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