Задача: 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(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun getAllElements(root1: TreeNode?, root2: TreeNode?): List<Int> {
        val stack1 = ArrayDeque<TreeNode>()
        val stack2 = ArrayDeque<TreeNode>()
        val output = mutableListOf<Int>()
        var root1 = root1
        var root2 = root2

        while (root1 != null

root2 != null

stack1.isNotEmpty() || stack2.isNotEmpty()) {
            while (root1 != null) {
                stack1.push(root1)
                root1 = root1.left
            }
            while (root2 != null) {
                stack2.push(root2)
                root2 = root2.left
            }
            if (stack2.isEmpty() || (stack1.isNotEmpty() && stack1.peek().`val` <= stack2.peek().`val`)) {
                root1 = stack1.pop()
                output.add(root1.`val`)
                root1 = root1.right
            } else {
                root2 = stack2.pop()
                output.add(root2.`val`)
                root2 = root2.right
            }
        }
        return output
    }
}

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