在两个二进制搜索树中打印公共节点

给定两个二进制搜索树，在其中查找公共节点。换句话说，找到两个BST的交点。

例子：

方法1（简单解决方案） 一种简单的方法是在第二棵树中逐个搜索第一棵树的每个节点。该解的时间复杂度为O（m*h），其中m是第一棵树中的节点数，h是第二棵树的高度。

方法2 :

• 方法—— 如果我们想到另一个问题，在这个问题中，我们有两个排序数组，我们必须找到它们之间的交集，我们可以很容易地使用双指针技术。现在我们可以很容易地把这个问题转化为上面的问题。我们知道，如果我们将BST的顺序遍历存储在数组中，那么该数组将按升序排序。所以我们能做的就是对这两棵树进行有序遍历，将它们存储在两个单独的数组中，然后找到两个数组之间的交集。
• 算法- 1） 按顺序遍历第一棵树，并将遍历存储在辅助数组ar1[]中。参见第1部分（订单） 在这里 . 2） 按顺序遍历第二棵树，并将遍历存储在辅助数组ar2[] 3） 找到ar1[]和ar2[]的交点。看见 这 详细信息。
• 复杂性分析：
  • 时间复杂性： O（m+n）。 这里‘m’和‘n’分别是第一棵树和第二棵树中的节点数，因为我们需要遍历这两棵树。
  • 辅助空间： 不使用任何数据结构来存储值-：O（m+n） 原因是我们需要两个单独的数组来存储这两棵树的有序遍历。

  方法3（线性时间和有限的额外空间） 这个想法是使用 迭代有序遍历
• 方法： 这里的想法是优化空间。在上面的方法中，我们存储树的所有元素，然后进行比较，但问题是存储所有元素真的有必要吗。我们可以做的是存储树的一个特定分支（最坏的情况是“树的高度”），然后开始比较。我们可以采用两个堆栈，并在各自的堆栈中按顺序存储树的遍历，但元素的最大数量应等于树的特定分支。分支一结束，我们就开始弹出并比较堆栈中的元素。现在如果 顶部（烟囱1） top（stack-1）的右分支中可以有更多大于它的元素，并且可以等于top（stack-2）。所以我们插入top（stack-1）的右分支，直到它等于NULL。在每次这样的插入结束时，我们要检查三个条件，然后在堆栈中进行相应的插入。

  if top(stack-1)<top(stack-2)
  root1=root1->right (then do insertions)
  
  if top(stack-1)>top(stack-2)
  root2=root2->right (then do insertions)
  
  else
  It's a match
  

  C++

  // C++ program of iterative traversal based method to // find common elements in two BSTs. #include<iostream> #include<stack> using namespace std; // A BST node struct Node { int key; struct Node *left, *right; }; // A utility function to create a new node Node *newNode( int ele) { Node *temp = new Node; temp->key = ele; temp->left = temp->right = NULL; return temp; } // Function two print common elements in given two trees void printCommon(Node *root1, Node *root2) { // Create two stacks for two inorder traversals stack<Node *> stack1, s1, s2; while (1) { // push the Nodes of first tree in stack s1 if (root1) { s1.push(root1); root1 = root1->left; } // push the Nodes of second tree in stack s2 else if (root2) { s2.push(root2); root2 = root2->left; } // Both root1 and root2 are NULL here else if (!s1.empty() && !s2.empty()) { root1 = s1.top(); root2 = s2.top(); // If current keys in two trees are same if (root1->key == root2->key) { cout << root1->key << " " ; s1.pop(); s2.pop(); // move to the inorder successor root1 = root1->right; root2 = root2->right; } else if (root1->key < root2->key) { // If Node of first tree is smaller, than that of // second tree, then its obvious that the inorder // successors of current Node can have same value // as that of the second tree Node. Thus, we pop // from s2 s1.pop(); root1 = root1->right; // root2 is set to NULL, because we need // new Nodes of tree 1 root2 = NULL; } else if (root1->key > root2->key) { s2.pop(); root2 = root2->right; root1 = NULL; } } // Both roots and both stacks are empty else break ; } } // A utility function to do inorder traversal void inorder( struct Node *root) { if (root) { inorder(root->left); cout<<root->key<< " " ; inorder(root->right); } } /* A utility function to insert a new Node with given key in BST */ struct Node* insert( struct Node* node, int key) { /* If the tree is empty, return a new Node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left  = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); /* return the (unchanged) Node pointer */ return node; } // Driver program int main() { // Create first tree as shown in example Node *root1 = NULL; root1 = insert(root1, 5); root1 = insert(root1, 1); root1 = insert(root1, 10); root1 = insert(root1,  0); root1 = insert(root1,  4); root1 = insert(root1,  7); root1 = insert(root1,  9); // Create second tree as shown in example Node *root2 = NULL; root2 = insert(root2, 10); root2 = insert(root2, 7); root2 = insert(root2, 20); root2 = insert(root2, 4); root2 = insert(root2, 9); cout << "Tree 1 : " ; inorder(root1); cout << endl; cout << "Tree 2 : " ; inorder(root2); cout << "Common Nodes: " ; printCommon(root1, root2); return 0; }

  JAVA

  // Java program of iterative traversal based method to // find common elements in two BSTs. import java.util.*; class GfG { // A BST node static class Node { int key; Node left, right; } // A utility function to create a new node static Node newNode( int ele) { Node temp = new Node(); temp.key = ele; temp.left = null ; temp.right = null ; return temp; } // Function two print common elements in given two trees static void printCommon(Node root1, Node root2) { Stack<Node> s1 = new Stack<Node> (); Stack<Node> s2 = new Stack<Node> (); while ( true ) { // push the Nodes of first tree in stack s1 if (root1 != null ) { s1.push(root1); root1 = root1.left; } // push the Nodes of second tree in stack s2 else if (root2 != null ) { s2.push(root2); root2 = root2.left; } // Both root1 and root2 are NULL here else if (!s1.isEmpty() && !s2.isEmpty()) { root1 = s1.peek(); root2 = s2.peek(); // If current keys in two trees are same if (root1.key == root2.key) { System.out.print(root1.key + " " ); s1.pop(); s2.pop(); // move to the inorder successor root1 = root1.right; root2 = root2.right; } else if (root1.key < root2.key) { // If Node of first tree is smaller, than that of // second tree, then its obvious that the inorder // successors of current Node can have same value // as that of the second tree Node. Thus, we pop // from s2 s1.pop(); root1 = root1.right; // root2 is set to NULL, because we need // new Nodes of tree 1 root2 = null ; } else if (root1.key > root2.key) { s2.pop(); root2 = root2.right; root1 = null ; } } // Both roots and both stacks are empty else break ; } } // A utility function to do inorder traversal static void inorder(Node root) { if (root != null ) { inorder(root.left); System.out.print(root.key + " " ); inorder(root.right); } } /* A utility function to insert a new Node with given key in BST */ static Node insert(Node node, int key) { /* If the tree is empty, return a new Node */ if (node == null ) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); /* return the (unchanged) Node pointer */ return node; } // Driver program public static void main(String[] args) { // Create first tree as shown in example Node root1 = null ; root1 = insert(root1, 5 ); root1 = insert(root1, 1 ); root1 = insert(root1, 10 ); root1 = insert(root1, 0 ); root1 = insert(root1, 4 ); root1 = insert(root1, 7 ); root1 = insert(root1, 9 ); // Create second tree as shown in example Node root2 = null ; root2 = insert(root2, 10 ); root2 = insert(root2, 7 ); root2 = insert(root2, 20 ); root2 = insert(root2, 4 ); root2 = insert(root2, 9 ); System.out.print( "Tree 1 : " + "" ); inorder(root1); System.out.println(); System.out.print( "Tree 2 : " + "" ); inorder(root2); System.out.println(); System.out.println( "Common Nodes: " ); printCommon(root1, root2); } }

  Python3

  # Python3 program of iterative traversal based # method to find common elements in two BSTs. # A utility function to create a new node class newNode: def __init__( self , key): self .key = key self .left = self .right = None # Function two print common elements # in given two trees def printCommon(root1, root2): # Create two stacks for two inorder # traversals s1 = [] s2 = [] while 1 : # append the Nodes of first # tree in stack s1 if root1: s1.append(root1) root1 = root1.left # append the Nodes of second tree # in stack s2 elif root2: s2.append(root2) root2 = root2.left # Both root1 and root2 are NULL here elif len (s1) ! = 0 and len (s2) ! = 0 : root1 = s1[ - 1 ] root2 = s2[ - 1 ] # If current keys in two trees are same if root1.key = = root2.key: print (root1.key, end = " " ) s1.pop( - 1 ) s2.pop( - 1 ) # move to the inorder successor root1 = root1.right root2 = root2.right elif root1.key < root2.key: # If Node of first tree is smaller, than # that of second tree, then its obvious # that the inorder successors of current # Node can have same value as that of the # second tree Node. Thus, we pop from s2 s1.pop( - 1 ) root1 = root1.right # root2 is set to NULL, because we need # new Nodes of tree 1 root2 = None elif root1.key > root2.key: s2.pop( - 1 ) root2 = root2.right root1 = None # Both roots and both stacks are empty else : break # A utility function to do inorder traversal def inorder(root): if root: inorder(root.left) print (root.key, end = " " ) inorder(root.right) # A utility function to insert a new Node # with given key in BST def insert(node, key): # If the tree is empty, return a new Node if node = = None : return newNode(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) # return the (unchanged) Node pointer return node # Driver Code if __name__ = = '__main__' : # Create first tree as shown in example root1 = None root1 = insert(root1, 5 ) root1 = insert(root1, 1 ) root1 = insert(root1, 10 ) root1 = insert(root1, 0 ) root1 = insert(root1, 4 ) root1 = insert(root1, 7 ) root1 = insert(root1, 9 ) # Create second tree as shown in example root2 = None root2 = insert(root2, 10 ) root2 = insert(root2, 7 ) root2 = insert(root2, 20 ) root2 = insert(root2, 4 ) root2 = insert(root2, 9 ) print ( "Tree 1 : " ) inorder(root1) print () print ( "Tree 2 : " ) inorder(root2) print () print ( "Common Nodes: " ) printCommon(root1, root2) # This code is contributed by PranchalK

  C#

  using System; using System.Collections.Generic; // C# program of iterative traversal based method to // find common elements in two BSTs. public class GfG { // A BST node public class Node { public int key; public Node left, right; } // A utility function to create a new node public static Node newNode( int ele) { Node temp = new Node(); temp.key = ele; temp.left = null ; temp.right = null ; return temp; } // Function two print common elements in given two trees public static void printCommon(Node root1, Node root2) { Stack<Node> s1 = new Stack<Node> (); Stack<Node> s2 = new Stack<Node> (); while ( true ) { // push the Nodes of first tree in stack s1 if (root1 != null ) { s1.Push(root1); root1 = root1.left; } // push the Nodes of second tree in stack s2 else if (root2 != null ) { s2.Push(root2); root2 = root2.left; } // Both root1 and root2 are NULL here else if (s1.Count > 0 && s2.Count > 0) { root1 = s1.Peek(); root2 = s2.Peek(); // If current keys in two trees are same if (root1.key == root2.key) { Console.Write(root1.key + " " ); s1.Pop(); s2.Pop(); // move to the inorder successor root1 = root1.right; root2 = root2.right; } else if (root1.key < root2.key) { // If Node of first tree is smaller, than that of // second tree, then its obvious that the inorder // successors of current Node can have same value // as that of the second tree Node. Thus, we pop // from s2 s1.Pop(); root1 = root1.right; // root2 is set to NULL, because we need // new Nodes of tree 1 root2 = null ; } else if (root1.key > root2.key) { s2.Pop(); root2 = root2.right; root1 = null ; } } // Both roots and both stacks are empty else { break ; } } } // A utility function to do inorder traversal public static void inorder(Node root) { if (root != null ) { inorder(root.left); Console.Write(root.key + " " ); inorder(root.right); } } /* A utility function to insert a new Node with given key in BST */ public static Node insert(Node node, int key) { /* If the tree is empty, return a new Node */ if (node == null ) { return newNode(key); } /* Otherwise, recur down the tree */ if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } /* return the (unchanged) Node pointer */ return node; } // Driver program public static void Main( string [] args) { // Create first tree as shown in example Node root1 = null ; root1 = insert(root1, 5); root1 = insert(root1, 1); root1 = insert(root1, 10); root1 = insert(root1, 0); root1 = insert(root1, 4); root1 = insert(root1, 7); root1 = insert(root1, 9); // Create second tree as shown in example Node root2 = null ; root2 = insert(root2, 10); root2 = insert(root2, 7); root2 = insert(root2, 20); root2 = insert(root2, 4); root2 = insert(root2, 9); Console.Write( "Tree 1 : " + "" ); inorder(root1); Console.WriteLine(); Console.Write( "Tree 2 : " + "" ); inorder(root2); Console.WriteLine(); Console.Write( "Common Nodes: " + "" ); printCommon(root1, root2); } } // This code is contributed by Shrikant13

  输出：

  4 7 9 10

• 复杂性分析：
  • 时间复杂性： O（n+m）。 这里‘m’和‘n’分别是第一棵树和第二棵树中的节点数，因为我们需要遍历这两棵树。
  • 辅助空间： 使用堆栈存储值，最多元素=‘树的高度’：O（h1+h2）

  本文由 埃克塔·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。