Объединить два BST с постоянным дополнительным пространством
Опубликовано: 13 Января, 2022
Учитывая два дерева двоичного поиска (BST), распечатайте элементы обоих BST в отсортированном виде.
Примечание : у обоих BST не будет общего элемента.
Примеры:
Вход
Первый BST :
3
/
1 5
Второй BST :
4
/
2 6
Выход : 1 2 3 4 5 6
Вход :
Первый BST :
8
/
2 10
/
1
Второй BST :
5
/
3
/
0
Выход : 0 1 2 3 5 8 10 Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Идея состоит в том, чтобы использовать тот факт, что крайний левый элемент (первый при обходе по порядку) дерева является наименьшим элементом в BST. Итак, мы вычисляем это значение для обоих деревьев и печатаем меньшее, теперь мы удаляем этот напечатанный элемент из соответствующего дерева и обновляем его. Затем мы рекурсивно вызываем нашу функцию с обновленным деревом. Делаем так до тех пор, пока одно из деревьев не истощится. Теперь мы просто печатаем обход другого дерева в порядке.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Structure of a BST Nodeclass Node {public: int data; Node* left; Node* right; Node(int x) { data = x; left = right = NULL; }};// A utility function to print// Inorder traversal of a Binary Treevoid inorder(Node* root){ if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); }}// The function to print data// of two BSTs in sorted ordervoid merge(Node* root1, Node* root2){ // Base cases if (!root1 && !root2) return; // If the first tree is exhausted // simply print the inorder // traversal of the second tree if (!root1) { inorder(root2); return; } // If second tree is exhausted // simply print the inoreder // traversal of the first tree if (!root2) { inorder(root1); return; } // A temporary pointer currently // pointing to root of first tree Node* temp1 = root1; // previous pointer to store the // parent of temporary pointer Node* prev1 = NULL; // Traverse through the first tree until you reach // the leftmost element, which is the first element // of the tree in the inorder traversal. // This is the least element of the tree while (temp1->left) { prev1 = temp1; temp1 = temp1->left; } // Another temporary pointer currently // pointing to root of second tree Node* temp2 = root2; // Previous pointer to store the // parent of second temporary pointer Node* prev2 = NULL; // Traverse through the second tree until you reach // the leftmost element, which is the first element of // the tree in inorder traversal. // This is the least element of the tree. while (temp2->left) { prev2 = temp2; temp2 = temp2->left; } // Compare the least current least // elements of both the tree if (temp1->data <= temp2->data) { // If first tree"s element is smaller print it cout << temp1->data << " "; // If the node has no parent, that // means this node is the root if (prev1 == NULL) { // Simply make the right // child of the root as new root merge(root1->right, root2); } // If node has a parent else { // As this node is the leftmost node, // it is certain that it will not have // a let child so we simply assign this // node"s right pointer, which can be // either null or not, to its parent"s left // pointer. This statement is // just doing the task of deleting the node prev1->left = temp1->right; // recursively call the merge // function with updated tree merge(root1, root2); } } else { cout << temp2->data << " "; // If the node has no parent, that // means this node is the root if (prev2 == NULL) { // Simply make the right child // of root as new root merge(root1, root2->right); } // If node has a parent else { prev2->left = temp2->right; // Recursively call the merge // function with updated tree merge(root1, root2); } }}// Driver Codeint main(){ Node *root1 = NULL, *root2 = NULL; root1 = new Node(3); root1->left = new Node(1); root1->right = new Node(5); root2 = new Node(4); root2->left = new Node(2); root2->right = new Node(6); // Print sorted nodes of both trees merge(root1, root2); return 0;} |
Java
// Java implementation of above approachimport java.util.*;class GFG{ // Structure of a BST Nodestatic class Node{ int data; Node left; Node right;};static Node newNode(int num){ Node temp = new Node(); temp.data = num; temp.left = temp.right = null; return temp;}// A utility function to print// Inorder traversal of a Binary Treestatic void inorder(Node root){ if (root != null) { inorder(root.left); System.out.print(root.data + " "); inorder(root.right); }}// The function to print data// of two BSTs in sorted orderstatic void merge(Node root1, Node root2){ // Base cases if (root1 == null && root2 == null) return; // If the first tree is exhausted // simply print the inorder // traversal of the second tree if (root1 == null) { inorder(root2); return; } // If second tree is exhausted // simply print the inoreder // traversal of the first tree if (root2 == null) { inorder(root1); return; } // A temporary pointer currently // pointing to root of first tree Node temp1 = root1; // previous pointer to store the // parent of temporary pointer Node prev1 = null; // Traverse through the first tree // until you reach the leftmost element, // which is the first element of the tree // in the inorder traversal. // This is the least element of the tree while (temp1.left != null) { prev1 = temp1; temp1 = temp1.left; } // Another temporary pointer currently // pointing to root of second tree Node temp2 = root2; // Previous pointer to store the // parent of second temporary pointer Node prev2 = null; // Traverse through the second tree // until you reach the leftmost element, // which is the first element of // the tree in inorder traversal. // This is the least element of the tree. while (temp2.left != null) { prev2 = temp2; temp2 = temp2.left; } // Compare the least current least // elements of both the tree if (temp1.data <= temp2.data) { // If first tree"s element is // smaller print it System.out.print(temp1.data + " "); // If the node has no parent, that // means this node is the root if (prev1 == null) { // Simply make the right // child of the root as new root merge(root1.right, root2); } // If node has a parent else { // As this node is the leftmost node, // it is certain that it will not have // a let child so we simply assign this // node"s right pointer, which can be // either null or not, to its parent"s left // pointer. This statement is // just doing the task of deleting the node prev1.left = temp1.right; // recursively call the merge // function with updated tree merge(root1, root2); } } else { System.out.print(temp2.data + " "); // If the node has no parent, that // means this node is the root if (prev2 == null) { // Simply make the right child // of root as new root merge(root1, root2.right); } // If node has a parent else { prev2.left = temp2.right; // Recursively call the merge // function with updated tree merge(root1, root2); } }}// Driver Codepublic static void main(String args[]){ Node root1 = null, root2 = null; root1 = newNode(3); root1.left = newNode(1); root1.right = newNode(5); root2 = newNode(4); root2.left = newNode(2); root2.right = newNode(6); // Print sorted nodes of both trees merge(root1, root2);}}// This code is contributed by ipg2016107 |
Python3
# Python3 implementation of above approach# Node of the binary treeclass node: def __init__ (self, key): self.data = key self.left = None self.right = None# A utility function to print# Inorder traversal of a Binary Treedef inorder(root): if (root != None): inorder(root.left) print(root.data, end = " ") inorder(root.right)# The function to print data# of two BSTs in sorted orderdef merge(root1, root2): # Base cases if (not root1 and not root2): return # If the first tree is exhausted # simply print the inorder # traversal of the second tree if (not root1): inorder(root2) return # If second tree is exhausted # simply print the inoreder # traversal of the first tree if (not root2): inorder(root1) return # A temporary pointer currently # pointing to root of first tree temp1 = root1 # previous pointer to store the # parent of temporary pointer prev1 = None # Traverse through the first tree # until you reach the leftmost # element, which is the first element # of the tree in the inorder traversal. # This is the least element of the tree while (temp1.left): prev1 = temp1 temp1 = temp1.left # Another temporary pointer currently # pointing to root of second tree temp2 = root2 # Previous pointer to store the # parent of second temporary pointer prev2 = None # Traverse through the second tree # until you reach the leftmost element, # which is the first element of the
РЕКОМЕНДУЕМЫЕ СТАТЬИ |