Hai BST tổng trong C ++

Giả sử chúng ta có hai cây tìm kiếm nhị phân, chúng ta phải trả về True iff có một nút trong cây đầu tiên và một nút trong cây thứ hai và tổng các nút này là một mục tiêu số nguyên cho trước . Vì vậy, nếu cây như -

và mục tiêu là 5, thì kết quả là true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ
• xác định một phương thức được gọi là check (), phương thức này sẽ lấy node, target và nodeNumber, phương thức này sẽ hoạt động như sau -
• nếu nút hợp lệ, thì trả về false
• curr:=giá trị của nút, req:=target - curr
• nếu req có trong s và s [req] không phải là nodeNumber, thì trả về true
• s [curr]:=nodeNumber
• kiểm tra trả về (bên trái của nút, đích, số nút) HOẶC kiểm tra (bên phải của nút, mục tiêu, số nút)
• Trong phương thức chính, chúng tôi sẽ đặt -
• flag:=check (root1, target, 1)
• kiểm tra trả lại (root2, target, 2)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
   }
};
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);
}

Đầu vào

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

Đầu ra

1