Проверьте, идентичны ли два дерева двоичного поиска или нет

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

Учитывая корневые узлы двух двоичных деревьев поиска. Задача состоит в том, чтобы вывести 1, если два дерева двоичного поиска идентичны, иначе выведите 0. Два дерева идентичны, если они идентичны структурно и узлы имеют одинаковые значения.

Дерево 1

Дерево 2

На изображениях выше Tree1 и Tree2 идентичны.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Чтобы определить, идентичны ли два дерева, нам нужно пройти оба дерева одновременно, и во время обхода нам нужно сравнить данные и дочерние элементы деревьев.

Ниже приведен пошаговый алгоритм проверки идентичности двух BST:

  1. Если оба дерева пусты, верните 1.
  2. Иначе Если оба дерева непусты
    • Проверить данные корневых узлов (tree1-> data == tree2-> data)
    • Рекурсивно проверять левые поддеревья, т.е. вызывать sameTree (tree1-> left_subtree, tree2-> left_subtree)
    • Проверять правые поддеревья рекурсивно, т.е. вызывать sameTree (tree1-> right_subtree, tree2-> right_subtree)
    • Если значения, возвращенные на трех вышеупомянутых шагах, верны, верните 1.
  3. В противном случае верните 0 (один пуст, а другой нет).

Below is the implementation of the above approach:

C++

// C++ program to check if two BSTs
// are identical
  
#include <iostream>
using namespace std;
  
// BST node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
  
// Utility function to create a new Node
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 to perform inorder traversal
void inorder(Node* root)
{
    if (root == NULL)
        return;
  
    inorder(root->left);
  
    cout << root->data << " ";
  
    inorder(root->right);
}
  
// Function to check if two BSTs
// are identical
int isIdentical(Node* root1, Node* root2)
{
    // Check if both the trees are empty
    if (root1 == NULL && root2 == NULL)
        return 1;
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != NULL && root2 == NULL)
        return 0;
    else if (root1 == NULL && root2 != NULL)
        return 0;
    else { // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1->data == root2->data && isIdentical(root1->left, root2->left)
            && isIdentical(root1->right, root2->right))
            return 1;
        else
            return 0;
    }
}
  
// Driver code
int main()
{
    struct Node* root1 = newNode(5);
    struct Node* root2 = newNode(5);
    root1->left = newNode(3);
    root1->right = newNode(8);
    root1->left->left = newNode(2);
    root1->left->right = newNode(4);
  
    root2->left = newNode(3);
    root2->right = newNode(8);
    root2->left->left = newNode(2);
    root2->left->right = newNode(4);
  
    if (isIdentical(root1, root2))
        cout << "Both BSTs are identical";
    else
        cout << "BSTs are not identical";
  
    return 0;
}

Java

// Java program to check if two BSTs
// are identical
class GFG
{
  
// BST node
static class Node 
{
    int data;
    Node left;
    Node right;
};
  
// Utility function to create a new Node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
  
    return node;
}
  
// Function to perform inorder traversal
static void inorder(Node root)
{
    if (root == null)
        return;
  
    inorder(root.left);
  
    System.out.print(root.data + " ");
  
    inorder(root.right);
}
  
// Function to check if two BSTs
// are identical
static int isIdentical(Node root1, 
                       Node root2)
{
    // Check if both the trees are empty
    if (root1 == null && root2 == null)
        return 1;
          
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != null && 
             root2 == null)
        return 0;
    else if (root1 == null && 
             root2 != null)
        return 0;
    else 
    { 
        // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1.data == root2.data && 
            isIdentical(root1.left, root2.left) == 1 && 
            isIdentical(root1.right, root2.right) == 1)
            return 1;
        else
            return 0;
    }
}
  
// Driver code
public static void main(String[] args)
{
    Node root1 = newNode(5);
    Node root2 = newNode(5);
    root1.left = newNode(3);
    root1.right = newNode(8);
    root1.left.left = newNode(2);
    root1.left.right = newNode(4);
  
    root2.left = newNode(3);
    root2.right = newNode(8);
    root2.left.left = newNode(2);
    root2.left.right = newNode(4);
  
    if (isIdentical(root1, root2)==1)
        System.out.print("Both BSTs are identical");
    else
        System.out.print("BSTs are not identical");
}
}
  
// This code is contributed by 29AjayKumar

Python3

# Python3 program to contrcut all unique
# BSTs for keys from 1 to n 
  
# Binary Tree Node 
""" A utility function to create a
new BST node """
class newNode: 
  
    # Construct to create a newNode 
    def __init__(self, data): 
        self.data = data
        self.left = None
        self.right = None
  
# Function to perform inorder traversal 
def inorder(root) :
  
    if (root == None): 
        return
  
    inorder(root.left) 
  
    print(root.data, end = " ") 
  
    inorder(root.right) 
  
# Function to check if two BSTs 
# are identical 
def isIdentical(root1, root2) :
  
    # Check if both the trees are empty 
    if (root1 == None and root2 == None) :
        return 1
          
    # If any one of the tree is non-empty 
    # and other is empty, return false 
    elif (root1 != None and root2 == None) :
        return 0
    elif (root1 == None and root2 != None) :
        return 0
    else: # Check if current data of both trees 
          # equal and recursively check for left 
          # and right subtrees 
        if (root1.data == root2.data and 
            isIdentical(root1.left, root2.left) 
            and isIdentical(root1.right, root2.right)) :
            return 1
        else:
            return 0
      
# Driver Code 
if __name__ == "__main__":
  
    root1 = newNode(5) 
    root2 = newNode(5) 
    root1.left = newNode(3) 
    root1.right = newNode(8) 
    root1.left.left = newNode(2) 
    root1.left.right = newNode(4) 
  
    root2.left = newNode(3) 
    root2.right = newNode(8) 
    root2.left.left = newNode(2) 
    root2.left.right = newNode(4) 
  
    if (isIdentical(root1, root2)): 
        print("Both BSTs are identical")
    else:
        print("BSTs are not identical")
  
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to check if two BSTs
// are identical
using System;
  
class GFG
{
  
// BST node
class Node 
{
    public int data;
    public Node left;
    public Node right;
};
  
// Utility function to create a new Node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
  
    return node;
}
  
// Function to perform inorder traversal
static void inorder(Node root)
{
    if (root == null)
        return;
  
    inorder(root.left);
  
    Console.Write(root.data + " ");
  
    inorder(root.right);
}
  
// Function to check if two BSTs
// are identical
static int isIdentical(Node root1, 
                       Node root2)
{
    // Check if both the trees are empty
    if (root1 == null && root2 == null)
        return 1;
          
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != null && 
             root2 == null)
        return 0;
    else if (root1 == null && 
             root2 != null)
        return 0;
    else
    { 
        // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1.data == root2.data && 
            isIdentical(root1.left, root2.left) == 1 && 
            isIdentical(root1.right, root2.right) == 1)
            return 1;
        else
            return 0;
    }
}
  
// Driver code
public static void Main(String[] args)
{
    Node root1 = newNode(5);
    Node root2 = newNode(5);
    root1.left = newNode(3);
    root1.right = newNode(8);
    root1.left.left = newNode(2);
    root1.left.right = newNode(4);
  
    root2.left = newNode(3);
    root2.right = newNode(8);
    root2.left.left = newNode(2);
    root2.left.right = newNode(4);
  
    if (isIdentical(root1, root2) == 1)
        Console.Write("Both BSTs are identical");
    else
        Console.Write("BSTs are not identical");
}
}
  
// This code is contributed by PrinciRaj1992
Output:
Both BSTs are identical

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

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

Различия между структурой данных массива и словаря
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