Two Sum ใน BST สองต้นใน C++

สมมติว่าเรามีต้นไม้ค้นหาทวิภาค (BST) สองต้น ต้องคืน true ก็ต่อเมื่อมีโหนดในต้นแรกและโหนดในต้นที่สองที่ผลรวมเท่ากับ target ที่กำหนด

ตัวอย่าง ต้นไม้ดังภาพ target = 5 ผลลัพธ์: true

ขั้นตอนการแก้ปัญหา (Hash Set + Tree Traversal)

• กำหนดแผนที่ s
• เมธอด check(node, target, nodeNumber):
  • ถ้า node ไม่มีอยู่ คืน false
  • curr := node.val, req := target - curr
  • ถ้า req อยู่ใน s และ s[req] != nodeNumber คืน true
  • s[curr] := nodeNumber
  • คืน check(left) OR check(right)
• เมธอดหลัก: เรียก check(root1, target, 1) แล้วตามด้วย check(root2, target, 2)

ตัวอย่างโค้ด (C++)

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        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:
    map <int,int> s;
    bool check(TreeNode* node, int target, int nodeNumber) {
        if(!node) return false;
        int curr = node->val;
        int req = target - curr;
        if(s.find(req) != s.end() && s[req] != nodeNumber) return true;
        s[curr] = nodeNumber;
        return check(node->left, target, nodeNumber) || check(node->right, target, nodeNumber);
    }
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        bool flag = check(root1, target, 1);
        return check(root2, target, 2);
    }
};

int main() {
    vector<int> v1 = {2,1,4};
    vector<int> v2 = {1,0,3};
    TreeNode *r1 = make_tree(v1);
    TreeNode *r2 = make_tree(v2);
    Solution ob;
    cout << ob.twoSumBSTs(r1, r2, 5);
}

อินพุต

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

เอาต์พุต

1