입력으로 두 개의 이진 탐색 트리와 변수 x가 제공됩니다. 목표는 노드 값의 합이 x와 같도록 각 트리에서 노드 쌍을 찾는 것입니다. BST_1의 노드 1과 BST_2의 노드 2를 가져와서 둘 다의 데이터 부분을 추가합니다. 합계=x인 경우. 증분 수.
예를 들어 이해합시다.
입력
출력 − 주어진 값 x와 합이 같은 두 BST의 쌍 수는 − 1
설명 - 쌍은 (8,6)
입력
출력 −합이 주어진 값 x와 동일한 두 BST의 쌍 수는 - 2입니다.
설명 - 쌍은 (5,15) 및 (4,16)
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 반복적인 inorder 방법을 사용하여 BST를 탐색할 것입니다. 반복적인 inorder 방법을 사용하여 가장 작은 노드에서 가장 큰 노드로 BST 1을 순회하고 반복적인 inorder 방법의 역에서 BST 2를 순회합니다. 두 BST의 현재 노드 합계를 구합니다. 합계가 x 증분 카운트인 경우. sum>x이면 BST 2에 있는 현재 노드의 하위 선행자로 이동합니다. sum
정수 데이터 부분과 자식 노드에 대한 왼쪽, 오른쪽 포인터가 있는 두 개의 트리 BST_1 및 BST_2를 가져옵니다.
insert_node(int data) 함수는 데이터가 있는 트리에 새 노드를 삽입하고 포인터를 반환합니다.
inser_node()를 사용하여 두 BST를 만들고 BST_sum_x(Tree* BST_1, Tree* BST_2, int x)에 전달합니다.
함수 BST_sum_x(Tree* BST_1, Tree* BST_2, int x)는 두 트리의 루트 노드를 가져와서 데이터 부분의 합이 x인 노드 쌍의 개수를 반환합니다.
합이 x인 쌍의 수에 대해 초기 계수를 0으로 취하십시오.
반복적인 inorder traversals는 두 개의 변수를 취합니다. Tree* stack_top_1, *stack_top_2;
두 개의 스택 스택 stack_1, stack_2를 만듭니다.
이제 외부 while 루프를 시작합니다.
while 루프를 사용하여 BST_1의 가장 왼쪽(가장 작은) 노드로 이동하고 모든 노드를 stack_1에 푸시합니다.
while 루프를 사용하여 BST_2의 가장 오른쪽(가장 큰) 노드로 이동하고 모든 노드를 stack_2로 푸시합니다.
스택 중 하나라도 비어 있으면 바깥쪽 while 루프를 끊습니다.
두 스택의 최상위 노드를 가져와서 데이터 부분을 추가하고 임시로 저장합니다.
temp ( sum) ==x이면 카운트를 증가시킵니다. 팝 작업을 사용하여 stack_1 및 stack_2 모두에서 최상위 요소를 제거합니다.
BST_1=stack_1->right 및 BST_2=stack_2->left로 설정(BST_1의 다음 후속 및 BST_2의 선행)
temp
IF temp>
x 그러면 stack_2에서 top만 제거하고 BST_1의 다음 선행 작업으로 이동합니다.
바깥쪽 while의 끝에서 count는 합이 x인 두 BST의 노드와 여러 쌍을 갖습니다.
결과로 카운트를 반환합니다.
위의 코드를 실행하면 다음 출력이 생성됩니다 -
예시
#include <bits/stdc++.h>
using namespace std;
struct Tree{
int data;
Tree* left, *right;
};
Tree* insert_node(int data){
Tree* newNode = (Tree*)malloc(sizeof(Tree));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
int count = 0;
Tree* stack_top_1, *stack_top_2;
stack<Tree*> stack_1, stack_2;
if (BST_1 == NULL || BST_2 == NULL){
return 0;
}
while (1){
while (BST_1 != NULL){
stack_1.push(BST_1);
BST_1 = BST_1->left;
}
while (BST_2 != NULL){
stack_2.push(BST_2);
BST_2 = BST_2->right;
}
if (stack_1.empty() || stack_2.empty()){
break;
}
stack_top_1 = stack_1.top();
stack_top_2 = stack_2.top();
int temp = stack_top_1->data + stack_top_2->data;
if (temp == x){
count++;
stack_1.pop();
stack_2.pop();
BST_1 = stack_top_1->right;
BST_2 = stack_top_2->left;
}
else if (temp < x){
stack_1.pop();
BST_1 = stack_top_1->right;
}
else{
stack_2.pop();
BST_2 = stack_top_2->left;
}
}
return count;
}
int main(){
//BST 1
Tree* BST_1 = insert_node(15);
BST_1->left = insert_node(10);
BST_1->right = insert_node(8);
BST_1->left->left = insert_node(12);
BST_1->left->right = insert_node(24);
BST_1->right->left = insert_node(16);
//BST 2
Tree* BST_2 = insert_node(20);
BST_2->left = insert_node(16);
BST_2->right = insert_node(4);
BST_2->left->left = insert_node(18);
BST_2->left->right = insert_node(28);
BST_2->right->left = insert_node(22);
int x = 28;
cout<<"Count of pairs from two BSTs whose sum is equal to a given value x ar: "<<BST_sum_x(BST_1, BST_2, x);
return 0;
} 출력
Count of pairs from two BSTs whose sum is equal to a given value x ar: 1