在C ++中的BST中找到具有给定总和的对
在本教程中，我们将编写一个程序，在二进制搜索树中找到总和等于给定数字的对。
我们将在两个不同的列表中存储树的值和树的值以查找对。让我们看看解决问题的步骤。
为二叉树创建一个结构节点。
编写一个函数以将新节点插入二进制搜索树。
请记住，在二叉搜索树中，所有小于root的元素都较小，而right则较大。
初始化两个空列表以存储树的左右节点。
遍历二进制搜索树，直到左或右节点为NULL或两个列表都不为空。
如果左侧节点值大于或等于右侧节点值，则中断循环。
如果两个值的和等于给定的数字，则打印并中断循环。
如果两个值的总和小于给定的数字，则从左侧列表中删除最后一个节点，然后移至该节点的右侧。
如果两个值的和大于给定的数字，则从右侧列表中删除最后一个节点，然后移至该节点的左侧。
编写一个循环以将所有元素存储到左侧节点列表中。
编写一个循环以将所有元素存储到正确的节点列表中。
从每个列表中获取最后一个节点。
检查两个值。
示例
让我们看一下代码。
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right, *root;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
root = NULL;
}
};
Node* insertNewNode(Node *root, int data){
if (root == NULL) {
root = new Node(data);
return root;
}
if (root->data < data) {
root->right = insertNewNode(root->right, data);
}
else if (root->data > data) {
root->left = insertNewNode(root->left, data);
}
return root;
}
void findThePairs(Node *node, int target) {
vector<Node*> left_side_nodes;
vector<Node*> right_side_nodes;
Node *current_left = node;
Node *current_right = node;
while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
while (current_left != NULL) {
left_side_nodes.push_back(current_left);
current_left = current_left->left;
}
while (current_right != NULL) {
right_side_nodes.push_back(current_right);
current_right = current_right->right;
}
Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
int left_side_value = left_side_node->data;
int right_side_value = right_side_node->data;
if (left_side_value >= right_side_value) {
break;
}
if (left_side_value + right_side_value < target) {
left_side_nodes.pop_back();
current_left = left_side_node->right;
}
else if (left_side_value + right_side_value > target) {
right_side_nodes.pop_back();
current_right = right_side_node->left;
}
else {
cout << left_side_node->data << " " << right_side_node->data << endl;
break;
}
}
}
int main() {
Node *root = NULL;
root = insertNewNode(root, 25);
root = insertNewNode(root, 20);
root = insertNewNode(root, 30);
root = insertNewNode(root, 15);
root = insertNewNode(root, 21);
root = insertNewNode(root, 19);
root = insertNewNode(root, 31);
findThePairs(root, 36);
}输出结果如果执行上述程序，将得到以下结果。
15 21