给两个 二进制搜索树（BST） 和一个给定的数目。任务是找到具有给定和的对，这样每个对元素必须位于不同的BST中。 例如：
null
Input : sum = 10 8 5 / / 3 10 2 18 / / 1 6 14 1 3 / / 5 7 13 4 Output : (5,5), (6,4), (7,3), (8,2)In above pairs first element lies in firstBST and second element lies in second BST
A. 简单解决方案 对于这个问题，将一棵树的遍历按顺序存储在辅助数组中，然后从数组中逐个选取元素，并在另一棵树中找到给定和的元素对。这种方法的时间复杂度为O（n 2. )如果两棵树中的节点总数相等。 一 有效解决方案 因为这个解决方案是将两个BST的顺序遍历存储在两个不同的辅助数组中 vect1[] 和vect2[]。现在我们跟着 方法1 属于 这 文章由于BST的顺序遍历总是给出排序序列，所以我们不需要对数组排序。
- 以迭代器为例 左边 并将其指向左边的vect1[]。
- 以迭代器为例 正当 并将其指向右角vect2[]。
- 现在如果 vect11[左]+vect2[右]
然后在vect1[]中向前移动左迭代器，即； 左++ . - 现在如果 vect1[左]+vect2[右]>和 然后向后移动vect[]中的右迭代器，即； 对—— .
下面是上述想法的实现。
C++
// C++ program to find pairs with given sum such // that one element of pair exists in one BST and // other in other BST. #include<bits/stdc++.h> using namespace std; // A binary Tree node struct Node { int data; struct Node *left, *right; }; // A utility function to create a new BST node // with key as given num struct Node* newNode( int num) { struct Node* temp = new Node; temp->data = num; temp->left = temp->right = NULL; return temp; } // A utility function to insert a given key to BST Node* insert(Node* root, int key) { if (root == NULL) return newNode(key); if (root->data > key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } // store storeInorder traversal in auxiliary array void storeInorder(Node *ptr, vector< int > &vect) { if (ptr==NULL) return ; storeInorder(ptr->left, vect); vect.push_back(ptr->data); storeInorder(ptr->right, vect); } // Function to find pair for given sum in different bst // vect1[] --> stores storeInorder traversal of first bst // vect2[] --> stores storeInorder traversal of second bst void pairSumUtil(vector< int > &vect1, vector< int > &vect2, int sum) { // Initialize two indexes to two different corners // of two vectors. int left = 0; int right = vect2.size() - 1; // find pair by moving two corners. while (left < vect1.size() && right >= 0) { // If we found a pair if (vect1[left] + vect2[right] == sum) { cout << "(" << vect1[left] << ", " << vect2[right] << "), " ; left++; right--; } // If sum is more, move to higher value in // first vector. else if (vect1[left] + vect2[right] < sum) left++; // If sum is less, move to lower value in // second vector. else right--; } } // Prints all pairs with given "sum" such that one // element of pair is in tree with root1 and other // node is in tree with root2. void pairSum(Node *root1, Node *root2, int sum) { // Store inorder traversals of two BSTs in two // vectors. vector< int > vect1, vect2; storeInorder(root1, vect1); storeInorder(root2, vect2); // Now the problem reduces to finding a pair // with given sum such that one element is in // vect1 and other is in vect2. pairSumUtil(vect1, vect2, sum); } // Driver program to run the case int main() { // first BST struct Node* root1 = NULL; root1 = insert(root1, 8); root1 = insert(root1, 10); root1 = insert(root1, 3); root1 = insert(root1, 6); root1 = insert(root1, 1); root1 = insert(root1, 5); root1 = insert(root1, 7); root1 = insert(root1, 14); root1 = insert(root1, 13); // second BST struct Node* root2 = NULL; root2 = insert(root2, 5); root2 = insert(root2, 18); root2 = insert(root2, 2); root2 = insert(root2, 1); root2 = insert(root2, 3); root2 = insert(root2, 4); int sum = 10; pairSum(root1, root2, sum); return 0; } |
JAVA
// Java program to find pairs with given sum such // that one element of pair exists in one BST and // other in other BST. import java.util.*; class solution { // A binary Tree node static class Node { int data; Node left, right; }; // A utility function to create a new BST node // with key as given num static Node newNode( int num) { Node temp = new Node(); temp.data = num; temp.left = temp.right = null ; return temp; } // A utility function to insert a given key to BST static Node insert(Node root, int key) { if (root == null ) return newNode(key); if (root.data > key) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; } // store storeInorder traversal in auxiliary array static void storeInorder(Node ptr, Vector<Integer> vect) { if (ptr== null ) return ; storeInorder(ptr.left, vect); vect.add(ptr.data); storeInorder(ptr.right, vect); } // Function to find pair for given sum in different bst // vect1.get() -. stores storeInorder traversal of first bst // vect2.get() -. stores storeInorder traversal of second bst static void pairSumUtil(Vector<Integer> vect1, Vector<Integer> vect2, int sum) { // Initialize two indexes to two different corners // of two Vectors. int left = 0 ; int right = vect2.size() - 1 ; // find pair by moving two corners. while (left < vect1.size() && right >= 0 ) { // If we found a pair if (vect1.get(left) + vect2.get(right) == sum) { System.out.print( "(" +vect1.get(left) + ", " + vect2.get(right) + "), " ); left++; right--; } // If sum is more, move to higher value in // first Vector. else if (vect1.get(left) + vect2.get(right) < sum) left++; // If sum is less, move to lower value in // second Vector. else right--; } } // Prints all pairs with given "sum" such that one // element of pair is in tree with root1 and other // node is in tree with root2. static void pairSum(Node root1, Node root2, int sum) { // Store inorder traversals of two BSTs in two // Vectors. Vector<Integer> vect1= new Vector<Integer>(), vect2= new Vector<Integer>(); storeInorder(root1, vect1); storeInorder(root2, vect2); // Now the problem reduces to finding a pair // with given sum such that one element is in // vect1 and other is in vect2. pairSumUtil(vect1, vect2, sum); } // Driver program to run the case public static void main(String args[]) { // first BST Node root1 = null ; root1 = insert(root1, 8 ); root1 = insert(root1, 10 ); root1 = insert(root1, 3 ); root1 = insert(root1, 6 ); root1 = insert(root1, 1 ); root1 = insert(root1, 5 ); root1 = insert(root1, 7 ); root1 = insert(root1, 14 ); root1 = insert(root1, 13 ); // second BST Node root2 = null ; root2 = insert(root2, 5 ); root2 = insert(root2, 18 ); root2 = insert(root2, 2 ); root2 = insert(root2, 1 ); root2 = insert(root2, 3 ); root2 = insert(root2, 4 ); int sum = 10 ; pairSum(root1, root2, sum); } } //contributed by Arnab Kundu |
Python3
# Python3 program to find pairs with given # sum such that one element of pair exists # in one BST and other in other BST. # A utility function to create a new # BST node with key as given num class newNode: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # A utility function to insert a # given key to BST def insert(root, key): if root = = None : return newNode(key) if root.data > key: root.left = insert(root.left, key) else : root.right = insert(root.right, key) return root # store storeInorder traversal in # auxiliary array def storeInorder(ptr, vect): if ptr = = None : return storeInorder(ptr.left, vect) vect.append(ptr.data) storeInorder(ptr.right, vect) # Function to find pair for given # sum in different bst # vect1[] --> stores storeInorder traversal # of first bst # vect2[] --> stores storeInorder traversal # of second bst def pairSumUtil(vect1, vect2, Sum ): # Initialize two indexes to two # different corners of two lists. left = 0 right = len (vect2) - 1 # find pair by moving two corners. while left < len (vect1) and right > = 0 : # If we found a pair if vect1[left] + vect2[right] = = Sum : print ( "(" , vect1[left], "," , vect2[right], ")," , end = " " ) left + = 1 right - = 1 # If sum is more, move to higher # value in first lists. elif vect1[left] + vect2[right] < Sum : left + = 1 # If sum is less, move to lower # value in second lists. else : right - = 1 # Prints all pairs with given "sum" such that one # element of pair is in tree with root1 and other # node is in tree with root2. def pairSum(root1, root2, Sum ): # Store inorder traversals of # two BSTs in two lists. vect1 = [] vect2 = [] storeInorder(root1, vect1) storeInorder(root2, vect2) # Now the problem reduces to finding a # pair with given sum such that one # element is in vect1 and other is in vect2. pairSumUtil(vect1, vect2, Sum ) # Driver Code if __name__ = = '__main__' : # first BST root1 = None root1 = insert(root1, 8 ) root1 = insert(root1, 10 ) root1 = insert(root1, 3 ) root1 = insert(root1, 6 ) root1 = insert(root1, 1 ) root1 = insert(root1, 5 ) root1 = insert(root1, 7 ) root1 = insert(root1, 14 ) root1 = insert(root1, 13 ) # second BST root2 = None root2 = insert(root2, 5 ) root2 = insert(root2, 18 ) root2 = insert(root2, 2 ) root2 = insert(root2, 1 ) root2 = insert(root2, 3 ) root2 = insert(root2, 4 ) Sum = 10 pairSum(root1, root2, Sum ) # This code is contributed by PranchalK |
C#
using System; using System.Collections.Generic; // C# program to find pairs with given sum such // that one element of pair exists in one BST and // other in other BST. public class solution { // A binary Tree node public class Node { public int data; public Node left, right; } // A utility function to create a new BST node // with key as given num public static Node newNode( int num) { Node temp = new Node(); temp.data = num; temp.left = temp.right = null ; return temp; } // A utility function to insert a given key to BST public static Node insert(Node root, int key) { if (root == null ) { return newNode(key); } if (root.data > key) { root.left = insert(root.left, key); } else { root.right = insert(root.right, key); } return root; } // store storeInorder traversal in auxiliary array public static void storeInorder(Node ptr, List< int > vect) { if (ptr == null ) { return ; } storeInorder(ptr.left, vect); vect.Add(ptr.data); storeInorder(ptr.right, vect); } // Function to find pair for given sum in different bst // vect1.get() -. stores storeInorder traversal of first bst // vect2.get() -. stores storeInorder traversal of second bst public static void pairSumUtil(List< int > vect1, List< int > vect2, int sum) { // Initialize two indexes to two different corners // of two Vectors. int left = 0; int right = vect2.Count - 1; // find pair by moving two corners. while (left < vect1.Count && right >= 0) { // If we found a pair if (vect1[left] + vect2[right] == sum) { Console.Write( "(" + vect1[left] + ", " + vect2[right] + "), " ); left++; right--; } // If sum is more, move to higher value in // first Vector. else if (vect1[left] + vect2[right] < sum) { left++; } // If sum is less, move to lower value in // second Vector. else { right--; } } } // Prints all pairs with given "sum" such that one // element of pair is in tree with root1 and other // node is in tree with root2. public static void pairSum(Node root1, Node root2, int sum) { // Store inorder traversals of two BSTs in two // Vectors. List< int > vect1 = new List< int >(), vect2 = new List< int >(); storeInorder(root1, vect1); storeInorder(root2, vect2); // Now the problem reduces to finding a pair // with given sum such that one element is in // vect1 and other is in vect2. pairSumUtil(vect1, vect2, sum); } // Driver program to run the case public static void Main( string [] args) { // first BST Node root1 = null ; root1 = insert(root1, 8); root1 = insert(root1, 10); root1 = insert(root1, 3); root1 = insert(root1, 6); root1 = insert(root1, 1); root1 = insert(root1, 5); root1 = insert(root1, 7); root1 = insert(root1, 14); root1 = insert(root1, 13); // second BST Node root2 = null ; root2 = insert(root2, 5); root2 = insert(root2, 18); root2 = insert(root2, 2); root2 = insert(root2, 1); root2 = insert(root2, 3); root2 = insert(root2, 4); int sum = 10; pairSum(root1, root2, sum); } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to find pairs with given sum such // that one element of pair exists in one BST and // other in other BST. // A binary Tree node class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } // A utility function to create a new BST node // with key as given num function newNode(num) { var temp = new Node(); temp.data = num; temp.left = temp.right = null ; return temp; } // A utility function to insert a given key to BST function insert(root, key) { if (root == null ) { return newNode(key); } if (root.data > key) { root.left = insert(root.left, key); } else { root.right = insert(root.right, key); } return root; } // store storeInorder traversal in auxiliary array function storeInorder(ptr, vect) { if (ptr == null ) { return ; } storeInorder(ptr.left, vect); vect.push(ptr.data); storeInorder(ptr.right, vect); } // Function to find pair for given sum in different bst // vect1.get() -. stores storeInorder traversal of first bst // vect2.get() -. stores storeInorder traversal of second bst function pairSumUtil(vect1, vect2, sum) { // Initialize two indexes to two different corners // of two Vectors. var left = 0; var right = vect2.length - 1; // find pair by moving two corners. while (left < vect1.length && right >= 0) { // If we found a pair if (vect1[left] + vect2[right] == sum) { document.write( "(" + vect1[left] + ", " + vect2[right] + "), " ); left++; right--; } // If sum is more, move to higher value in // first Vector. else if (vect1[left] + vect2[right] < sum) { left++; } // If sum is less, move to lower value in // second Vector. else { right--; } } } // Prints all pairs with given "sum" such that one // element of pair is in tree with root1 and other // node is in tree with root2. function pairSum(root1, root2, sum) { // Store inorder traversals of two BSTs in two // Vectors. var vect1 = [], vect2 = []; storeInorder(root1, vect1); storeInorder(root2, vect2); // Now the problem reduces to finding a pair // with given sum such that one element is in // vect1 and other is in vect2. pairSumUtil(vect1, vect2, sum); } // Driver program to run the case // first BST var root1 = null ; root1 = insert(root1, 8); root1 = insert(root1, 10); root1 = insert(root1, 3); root1 = insert(root1, 6); root1 = insert(root1, 1); root1 = insert(root1, 5); root1 = insert(root1, 7); root1 = insert(root1, 14); root1 = insert(root1, 13); // second BST var root2 = null ; root2 = insert(root2, 5); root2 = insert(root2, 18); root2 = insert(root2, 2); root2 = insert(root2, 1); root2 = insert(root2, 3); root2 = insert(root2, 4); var sum = 10; pairSum(root1, root2, sum); </script> |
输出：
(5,5),(6,4),(7,3),(8,2)
时间复杂性： O（n） 辅助空间： O（n） 我们还有一个 空间优化 解决这个问题的方法。我们的想法是 将bst转换为双链表 并将上述方法应用于双链表。看见 这 文章 时间复杂性： O（n） 辅助空间： O（1） 本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
