Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private function dfs($node, &$nodeSet) {
        if ($node === null) return;
        $this->dfs($node->left, $nodeSet);
        $nodeSet[] = $node->val;
        $this->dfs($node->right, $nodeSet);
    }

    function twoSumBSTs($root1, $root2, $target) {
        $nodeSet1 = [];
        $nodeSet2 = [];
        $this->dfs($root1, $nodeSet1);
        $this->dfs($root2, $nodeSet2);
        
        foreach ($nodeSet1 as $value1) {
            if (in_array($target - $value1, $nodeSet2)) {
                return true;
            }
        }
        
        return false;
    }
}

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