Hai tổng IV - Đầu vào là một BST trong C ++

Giả sử chúng ta có một Cây tìm kiếm nhị phân và một giá trị đích; chúng tôi phải kiểm tra xem có tồn tại hai phần tử trong BST sao cho tổng của chúng bằng với mục tiêu đã cho hay không.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ 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 mảng v
Xác định một hàm inorder (), hàm này sẽ bắt nguồn từ gốc,
nếu root là null, thì -
- trở lại
inorder (bên trái của thư mục gốc)
chèn giá trị của root vào v
inorder (bên trái của thư mục gốc)
Xác định một hàm findnode (), điều này sẽ lấy k,
n:=kích thước của v
trong khi tôi
- t:=v [i] + v [j]
- nếu t giống với k, thì -
  - trả về true
- nếu t
  - (tăng tôi lên 1)
- Nếu không
  - (giảm j đi 1)
trả về false
Từ phương thức chính, hãy làm như sau -
inorder (gốc)
sắp xếp mảng v
trả về findnode (k)

Ví dụ

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:
   vector<int> v;
   void inorder(TreeNode* root){
      if (root == NULL || root->val == 0)
         return;
      inorder(root->left);
      v.push_back(root->val);
      inorder(root->right);
   }
   bool findnode(int k){
      int n = v.size(), i = 0, j = n - 1;
      while (i < j) {
         int t = v[i] + v[j];
         if (t == k)
            return true;
         if (t < k)
            i++;
         else
            j--;
      }
      return false;
   }
   bool findTarget(TreeNode* root, int k){
      inorder(root);
      sort(v.begin(), v.end());
      return findnode(k);
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,6,2,4,NULL,7};
   TreeNode *root = make_tree(v);
   cout << (ob.findTarget(root, 9));
}

Đầu vào

{5,3,6,2,4,NULL,7},9

Hai tổng IV - Đầu vào là một BST trong C ++

Ví dụ

Đầu vào

Đầu ra