Задача: 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:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> stack1, stack2;
        vector<int> output;

        while (root1 || root2 || !stack1.empty() || !stack2.empty()) {
            while (root1) {
                stack1.push(root1);
                root1 = root1->left;
            }
            while (root2) {
                stack2.push(root2);
                root2 = root2->left;
            }
            if (stack2.empty() || (!stack1.empty() && stack1.top()->val <= stack2.top()->val)) {
                root1 = stack1.top();
                stack1.pop();
                output.push_back(root1->val);
                root1 = root1->right;
            } else {
                root2 = stack2.top();
                stack2.pop();
                output.push_back(root2->val);
                root2 = root2->right;
            }
        }
        return output;
    }
};

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