Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

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

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список.

3⃣Верните выходной список.

😎 Решение:

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

class Solution {
    function getAllElements($root1, $root2) {
        $stack1 = new SplStack();
        $stack2 = new SplStack();
        $output = [];

        while ($root1 !== null || $root2 !== null || !$stack1->isEmpty() || !$stack2->isEmpty()) {
            while ($root1 !== null) {
                $stack1->push($root1);
                $root1 = $root1->left;
            }
            while ($root2 !== null) {
                $stack2->push($root2);
                $root2 = $root2->left;
            }
            if ($stack2->isEmpty() || (!$stack1->isEmpty() && $stack1->top()->val <= $stack2->top()->val)) {
                $root1 = $stack1->pop();
                $output[] = $root1->val;
                $root1 = $root1->right;
            } else {
                $root2 = $stack2->pop();
                $output[] = $root2->val;
                $root2 = $root2->right;
            }
        }
        return $output;
    }
}

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