Два узла BST поменялись местами, исправьте BST | Комплект-2
Дано двоичное дерево поиска с двумя замененными узлами двоичного дерева поиска (BST). Задача - исправить (или исправить) BST.
Примечание : у BST не будет дубликатов.
Примеры :
Входное дерево : 10 / 5 8 / 2 20 В приведенном выше дереве необходимо поменять местами узлы 20 и 8, чтобы исправить дерево. Ниже приведено дерево вывода 10 / 5 20 / 2 8
Подход:
- Пройдите через BST по порядку и сохраните узлы в векторе.
- Затем этот вектор сортируется после создания его копии.
- Используйте сортировку вставкой, так как она работает лучше всего и быстрее всего, когда массив почти отсортирован. Как и в этой задаче, будут перемещены только два элемента, поэтому сортировка вставкой здесь будет работать за линейное время.
- После сортировки сравните отсортированный вектор и копию вектора, созданного ранее, тем самым найдите узлы с ошибками и исправьте их, найдя их в дереве и обменяв их.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // A binary tree node has data, pointer // to left child and a pointer to right child struct node { int data; struct node *left, *right; node( int x) { data = x; left = right = NULL; } }; // Utility function for insertion sort void insertionSort(vector< int >& v, int n) { int i, key, j; for (i = 1; i < n; i++) { key = v[i]; j = i - 1; while (j >= 0 && v[j] > key) { v[j + 1] = v[j]; j = j - 1; } v[j + 1] = key; } } // Utility function to create a vector // with inorder traversal of a binary tree void inorder(node* root, vector< int >& v) { // Base cases if (!root) return ; // Recursive call for left subtree inorder(root->left, v); // Insert node into vector v.push_back(root->data); // Recursive call for right subtree inorder(root->right, v); } // Function to exchange data // for incorrect nodes void find(node* root, int res, int res2) { // Base cases if (!root) { return ; } // Recursive call to find // the node in left subtree find(root->left, res, res2); // Check if current node // is incorrect and exchange if (root->data == res) { root->data = res2; } else if (root->data == res2) { root->data = res; } // Recurive call to find // the node in right subtree find(root->right, res, res2); } // Primary function to fix the two nodes struct node* correctBST( struct node* root) { // Vector to store the // inorder traversal of tree vector< int > v; // Function call to insert // nodes into vector inorder(root, v); // create a copy of the vector vector< int > v1 = v; // Sort the original vector thereby // making it a valid BST"s inorder insertionSort(v, v.size()); // Traverse through both vectors and // compare misplaced values in original BST for ( int i = 0; i < v.size(); i++) { // Find the mismatched values // and interchange them if (v[i] != v1[i]) { // Find and exchange the // data of the two nodes find(root, v1[i], v[i]); // As it given only two values are // wrong we don"t need to check further break ; } } // Return the root of corrected BST return root; } // A utility function to // print Inorder traversal void printInorder( struct node* node) { if (node == NULL) return ; printInorder(node->left); printf ( "%d " , node->data); printInorder(node->right); } int main() { struct node* root = new node(6); root->left = new node(10); root->right = new node(2); root->left->left = new node(1); root->left->right = new node(3); root->right->right = new node(12); root->right->left = new node(7); printf ( "Inorder Traversal of the" ); printf ( "original tree
" ); printInorder(root); correctBST(root); printf ( "
Inorder Traversal of the" ); printf ( "fixed tree
" ); printInorder(root); return 0; } |
Java
// Java implementation of the above approach import java.util.ArrayList; class GFG { // A binary tree node has data, pointer // to left child and a pointer to right child static class node { int data; node left, right; public node( int x) { data = x; left = right = null ; } }; // Utility function for insertion sort static void insertionSort(ArrayList<Integer> v, int n) { int i, key, j; for (i = 1 ; i < n; i++) { key = v.get(i); j = i - 1 ; while (j >= 0 && v.get(j) > key) { v.set(j + 1 , v.get(i)); j = j - 1 ; } v.set(j + 1 , key); } } // Utility function to create a vector // with inorder traversal of a binary tree static void inorder(node root, ArrayList<Integer> v) { // Base cases if (root == null ) return ; // Recursive call for left subtree inorder(root.left, v); // Insert node into vector v.add(root.data); // Recursive call for right subtree inorder(root.right, v); } // Function to exchange data // for incorrect nodes static void find(node root, int res, int res2) { // Base cases if (root == null ) { return ; } // Recursive call to find // the node in left subtree find(root.left, res, res2); // Check if current node // is incorrect and exchange if (root.data == res) { root.data = res2; } else if (root.data == res2) { root.data = res; } // Recursive call to find // the node in right subtree find(root.right, res, res2); } // Primary function to fix the two nodes static node correctBST(node root) { // Vector to store the // inorder traversal of tree ArrayList<Integer> v = new ArrayList<>(); // Function call to insert // nodes into vector inorder(root, v); // create a copy of the vector ArrayList<Integer> v1 = new ArrayList<>(v); // Sort the original vector thereby // making it a valid BST"s inorder insertionSort(v, v.size()); // Traverse through both vectors and // compare misplaced values in original BST for ( int i = 0 ; i < v.size(); i++) { // Find the mismatched values // and interchange them if (v.get(i) != v1.get(i)) { // Find and exchange the // data of the two nodes find(root, v1.get(i), v.get(i)); // As it given only two values are // wrong we don"t need to check further break ; } } // Return the root of corrected BST return root; } // A utility function to // print Inorder traversal static void printInorder(node node) { if (node == null ) return ; printInorder(node.left); System.out.printf( "%d " , node.data); printInorder(node.right); } // Driver code public static void main(String[] args) { node root = new node( 6 ); root.left = new node( 10 ); root.right = new node( 2 ); root.left.left = new node( 1 ); root.left.right = new node( 3 ); root.right.right = new node( 12 ); root.right.left = new node( 7 ); System.out.printf( "Inorder Traversal of the" ); System.out.printf( "original tree
" ); printInorder(root); correctBST(root); System.out.printf( "
Inorder Traversal of the" ); System.out.printf( "fixed tree
" ); printInorder(root); } } // This code is contributed by sanjeev2552 |
Inorder Traversal of theoriginal tree 1 10 3 6 7 2 12 Inorder Traversal of thefixed tree 1 2 3 6 7 10 12
Сложность времени: O (N)
Вспомогательное пространство: O (N), где N - количество узлов в двоичном дереве.
Способ 2:
Чтобы понять это, вам нужно сначала понять Morris Traversalor Morris Threading Traversal. Он использует указатель вправо / влево конечных узлов для достижения обхода пространства O (1) в двоичном дереве.
Таким образом, в этом подходе мы можем решить эту проблему за время O (n) и пространство O (1), то есть в постоянном пространстве , с одним обходом данного BST. Поскольку неупорядоченный обход BST всегда представляет собой отсортированный массив, проблема может быть сведена к проблеме, когда два элемента отсортированного массива меняются местами.
Below is the implementation of the above approach:
C++
// C++ implementation of the // above approach #include <bits/stdc++.h> using namespace std ; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node *left, *right; }; // A utility function to swap two integers void swap( int * a, int * b ) { int t = *a; *a = *b; *b = t; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node *) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Function for inorder traversal using // Morris Traversal void MorrisTraversal( struct node* root, struct node* &first, struct node* &last, struct node* &prev ) { // Current node struct node* curr = root; while (curr != NULL) { if (curr->left==NULL) { // If this node is smaller than // the previous node, it"s // violating the BST rule. if (first == NULL && prev != NULL && prev->data > curr->data) { // If this is first violation, // mark these two nodes as // "first" and "last" first = prev; last = curr; } if (first != NULL && prev->data > curr->data) { // If this is second violation, // mark this node as last &nbs
РЕКОМЕНДУЕМЫЕ СТАТЬИ |