Два узла BST поменялись местами, исправьте BST | Комплект-2

Опубликовано: 13 Января, 2022

Дано двоичное дерево поиска с двумя замененными узлами двоичного дерева поиска (BST). Задача - исправить (или исправить) BST.
Примечание : у BST не будет дубликатов.
Примеры :

 Входное дерево :
         10
        / 
       5 8
      / 
     2 20

В приведенном выше дереве необходимо поменять местами узлы 20 и 8, чтобы исправить дерево.  
Ниже приведено дерево вывода
         10
        / 
       5 20
      / 
     2 8
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  • Пройдите через 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
Output
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
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022