Tất cả phần tử trong hai cây tìm kiếm nhị phân trong C++

Cho hai cây tìm kiếm nhị phân (BST), trả về danh sách tất cả giá trị có trong cả hai cây theo thứ tự tăng dần.

Ví dụ với hai cây:

Kết quả: [0,1,1,2,3,4].

Giải thuật (Duyệt inorder song song)

1. Khởi tạo mảng ans, hai ngăn xếp st1, st2.
2. curr1 = root1, curr2 = root2.
3. Đẩy root1 và tất cả nút con trái vào st1, tương tự cho root2 vào st2.
4. Khi st1 hoặc st2 không rỗng:
5. Nếu st1 không rỗng và (st2 rỗng hoặc đỉnh st1 ≤ đỉnh st2):
6. Lấy temp = đỉnh st1, pop.
7. Thêm giá trị temp vào ans.
8. Đẩy nút phải của temp và tất cả con trái vào st1.
9. Ngược lại, làm tương tự với st2.
10. Trả về ans.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else q.push(temp->right);
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

class Solution {
public:
    void pushLeft(stack<TreeNode*>& st, TreeNode* root) {
        TreeNode* curr = root;
        while(curr) { st.push(curr); curr = curr->left; }
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> ans;
        stack<TreeNode*> st1, st2;
        pushLeft(st1, root1);
        pushLeft(st2, root2);
        while(!st1.empty() || !st2.empty()) {
            TreeNode* temp;
            if(!st1.empty() && (st2.empty() || st1.top()->val <= st2.top()->val)) {
                temp = st1.top(); st1.pop();
                ans.push_back(temp->val);
                pushLeft(st1, temp->right);
            } else {
                temp = st2.top(); st2.pop();
                ans.push_back(temp->val);
                pushLeft(st2, temp->right);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v = {2,1,4};
    TreeNode *root1 = make_tree(v);
    v = {1,0,3};
    TreeNode *root2 = make_tree(v);
    Solution ob;
    print_vector(ob.getAllElements(root1, root2));
    return 0;
}

Đầu vào

[2,1,4] [1,0,3]

Đầu ra

[0,1,1,2,3,4]