Рубрики

Проверьте, является ли обход двух бинарных деревьев одним и тем же?

Обход листьев — это последовательность листьев, пересекаемых слева направо. Проблема состоит в том, чтобы проверить, являются ли обходы двух данных двоичных деревьев одинаковыми или нет.

Ожидаемая временная сложность O (n). Ожидаемое вспомогательное пространство O (h1 + h2), где h1 и h2 — высоты двух двоичных деревьев.

Примеры:

Input: Roots of below Binary Trees
         1            
    / \
       2   3      
      /   / \          
     4   6   7

     0
    /  \
       5    8      
        \  / \        
        4  6  7
Output: same
Leaf order traversal of both trees is 4 6 7     

Input: Roots of below Binary Trees
         0            
    / \
       1   2       
      / \       
     8   9   

     1
    / \
       4   3     
        \ / \        
        8 2  9

Output: Not Same
Leaf traversals of two trees are different.
For first, it is 8 9 2 and for second it is
8 2 9

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.
Простое решение — это обход первого дерева и сохранение листьев слева и справа в массиве. Затем пройдитесь по другому дереву и сохраните листья в другом массиве. Наконец, сравните два массива. Если оба массива одинаковы, вернуть true.

Приведенное выше решение требует O (m + n) дополнительного пространства, где m и n — узлы в первом и втором дереве соответственно.

Как проверить с O (h1 + h2) пробел?
Идея заключается в использовании итеративного обхода. Пройдите по обоим деревьям одновременно, найдите узел листьев в обоих деревьях и сравните найденные листья. Все листья должны совпадать.

Алгоритм:

1. Create empty stacks stack1 and stack2 
   for iterative traversals of tree1 and tree2

2. insert (root of tree1) in stack1
   insert (root of tree2) in stack2

3. Stores current leaf nodes of tree1 and tree2
temp1 = (root of tree1) 
temp2 = (root of tree2)  

4. Traverse both trees using stacks
while (stack1 and stack2 parent empty) 
{
    // Means excess leaves in one tree
    if (if one of the stacks are empty)   
    return false

   // get next leaf node in tree1 
   temp1 = stack1.pop()
   while (temp1 is not leaf node) 
   {
        push right child to stack1     
    push left child to stack1
   }

   // get next leaf node in tree2     
   temp2 = stack2.pop()
   while (temp2 is not leaf node) 
   {
        push right child to stack2      
    push left child to stack2
   }

   // If leaves do not match return false
   if (temp1 != temp2)                  
       return false
}

5. If all leaves matched, return true

Ниже приведена реализация вышеуказанного алгоритма на Java.

C ++

// C ++ код для проверки обхода листьев
// из двух двоичных деревьев одинаковы или нет.
#include<bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int data;

    Node* left;

    Node* right;

};

  
// Возвращает новый узел с данными как
// ввод в функцию ниже.

Node* newNode(int d)

{

    Node* temp = new Node;

    temp->data = d;

    temp->left = NULL;

    temp->right = NULL;

      

    return temp; 

}

  
// проверяет, является ли данный узел листовым или нет.

bool isLeaf(Node* root)

{

    if(root == NULL)

        return false;

    if(!root->left && !root->right)

        return true;

    return false;

}

  
// итерационная функция.
// возвращает true, если обход листьев
// одинаковы, иначе ложь.

bool isSame(Node* root1, Node* root2)

{

    stack<Node*> s1;

    stack<Node*> s2;

      

    // помещаем root1 в пустой стек s1.

    s1.push(root1);

      

    // помещаем root2 в пустой стек s2.

    s2.push(root2);

      

    // цикл до тех пор, пока один из стеков не будет пустым.

    while(!s1.empty() || !s2.empty())

    {

        // это означает, что один из стеков имеет

        // лишние листья, следовательно, возвращаем false.

        if(s1.empty() || s2.empty())

            return false;

              

        Node* temp1 = s1.top();

        s1.pop();

        while(temp1 != NULL && !isLeaf(temp1))

        {

            // Нажмите правого потомка, если существует

            if(temp1->right)

                s1.push(temp1->right);

                  

            // Нажмите левого потомка, если существует

            if(temp1->left)

                s1.push(temp1->left);

                  

            // Обратите внимание, что правильный ребенок (если существует)

            // помещается перед левым потомком (если существует).

            temp1 = s1.top();

            s1.pop();

        }

          

        Node* temp2 = s2.top();

        while(temp2 != NULL && !isLeaf(temp2))

        {

            // Нажмите правого потомка, если существует

            if(temp2->right)

                s2.push(temp2->right);

                  

            // Нажмите левого потомка, если существует

            if(temp2->left)

                s2.push(temp2->left);

            temp2 = s2.top();

            s2.pop();

        }

          

        if(!temp1 && temp2)

            return false;

        if(temp1 && !temp2)

            return false;

        if(temp1 && temp2)

        {

            return temp1->data == temp2->data;

        }

    }

      

    // все листья совпадают

    return true;

}

  
// Код драйвера

int main()

{

    Node* root1 = newNode(1);

    root1->left = newNode(2);

    root1->right = newNode(3);

    root1->left->left = newNode(4);

    root1->right->left = newNode(6);

    root1->right->right = newNode(7);

      

    Node* root2 = newNode(0);

    root2->left = newNode(1);

    root2->right = newNode(5);

    root2->left->right = newNode(4);

    root2->right->left = newNode(6);

    root2->right->right = newNode(7);

      

    if(isSame(root1, root2))

        cout << "Same";

    else

        cout << "Not Same";

    return 0;

}

  
// Этот код добавлен
// Ааста Варма

Джава

// Java-программа для проверки наличия двух листовых обходов
// Два двоичных дерева одинаковы или нет

import java.util.*;

import java.lang.*;

import java.io.*;

  
// Узел двоичного дерева

class Node

{

   int data;

   Node left, right;

   public Node(int x)

   {

      data = x;

      left = right = null;

   }

   public boolean isLeaf()

   {

      return (left==null && right==null);

   }

}

  

class LeafOrderTraversal

{

   // Возвращает true для обхода двух деревьев

   // то же самое, иначе ложь

   public static boolean isSame(Node root1, Node root2)

   {

      // Создать пустые стеки. Эти стеки собираются

      // для использования в итеративных обходах.

      Stack<Node> s1 = new Stack<Node>();

      Stack<Node> s2 = new Stack<Node>();

  

      s1.push(root1);

      s2.push(root2);

  

      // Цикл, пока один из двух стеков не будет пустым

      while (!s1.empty() || !s2.empty())

      {

         // Если один из стеков пуст, значит другой

         // в стеке есть дополнительные листья, поэтому возвращаем false

         if (s1.empty() || s2.empty())

            return false;

  

         Node temp1 = s1.pop();

         while (temp1!=null && !temp1.isLeaf())

         {

            // Нажать правую и левую дочерние элементы temp1.

            // Обратите внимание, что правый потомок вставлен

            // перед тем как уйти

            if (temp1.right != null)

               s1.push(temp1. right);

            if (temp1.left != null)

               s1.push(temp1.left);

            temp1 = s1.pop();

         }

  

         // то же самое для tree2

         Node temp2 = s2.pop();

         while (temp2!=null && !temp2.isLeaf())

         {

            if (temp2.right != null)

               s2.push(temp2.right);

            if (temp2.left != null)

               s2.push(temp2.left);

            temp2 = s2.pop();

         }

  

         // Если один равен нулю, а другой нет, тогда

         // вернуть ложь

         if (temp1==null && temp2!=null)

            return false;

         if (temp1!=null && temp2==null)

            return false;

  

         // Если оба не равны NULL и данные не

         // то же возвращаемое значение false

         if (temp1!=null && temp2!=null)

         {

            if (temp1.data != temp2.data)

               return false;

         }

      }

  

      // Если управление достигает этой точки, все уходит

      // совпадают

      return true;

   }

  

   // Программа драйвера для тестирования

   public static void main(String[] args)

   {

      // Давайте создадим деревья в примере выше 1

      Node root1 = new Node(1);

      root1.left = new Node(2);

      root1.right = new Node(3);

      root1.left.left = new Node(4);

      root1.right.left = new Node(6);

      root1.right.right = new Node(7);

  

      Node root2 = new Node(0);

      root2.left = new Node(1);

      root2.right = new Node(5);

      root2.left.right = new Node(4);

      root2.right.left = new Node(6);

      root2.right.right = new Node(7);

  

      if (isSame(root1, root2))

         System.out.println("Same");

      else

         System.out.println("Not Same");

   }

}

python3

# Python3 программа для проверки, если два листа
# Обход двух двоичных деревьев одинаков или нет

  
# Узел двоичного дерева

class Node:

    def __init__(self, x):

        self.data = x

        self.left = self.right = None

    def isLeaf(self):

        return (self.left == None and 

                self.right == None)

                  
# Возвращает true для обхода листа
# два дерева одинаковы, иначе ложь

def isSame(root1, root2):

      

    # Создание пустых стеков. Эти стеки собираются

    # для использования в итеративных обходах.

    s1 = []

    s2 = []

  

    s1.append(root1) 

    s2.append(root2) 

  

    # Цикл до двух стеков

    # не пусто

    while (len(s1) != 0 or len(s2) != 0):

          

        # Если один из стеков пуст, значит другой

        # стек имеет лишние листья, поэтому возвращает false

        if (len(s1) == 0 or len(s2) == 0): 

            return False

  

        temp1 = s1.pop(-1

        while (temp1 != None and not temp1.isLeaf()):

              

            # добавить правые и левые дочерние элементы temp1.

            # Обратите внимание, что правильный ребенок вставлен

            # перед уходом

            if (temp1.right != None): 

                s1.append(temp1. right) 

            if (temp1.left != None): 

                s1.append(temp1.left) 

                temp1 = s1.pop(-1)

  

        # то же самое для tree2

        temp2 = s2.pop(-1

        while (temp2 != None and not temp2.isLeaf()):

            if (temp2.right != None): 

                s2.append(temp2.right) 

            if (temp2.left != None):

                s2.append(temp2.left) 

            temp2 = s2.pop(-1)

  

        # Если один Нет, а другой нет,

        # затем вернуть false

        if (temp1 == None and temp2 != None): 

            return False

        if (temp1 != None and temp2 == None): 

            return False

  

        # Если оба не None и данные

        # не то же самое возвращение ложного

        if (temp1 != None and temp2 != None):

            if (temp1.data != temp2.data): 

                return False

  

    # Если контроль достигает этой точки,

    # все листья совпадают

    return True

  
Код водителя

if __name__ == '__main__':

      

    # Давайте создадим деревья в примере выше 1

    root1 = Node(1

    root1.left = Node(2

    root1.right = Node(3

    root1.left.left = Node(4

    root1.right.left = Node(6

    root1.right.right = Node(7

  

    root2 = Node(0

    root2.left = Node(1

    root2.right = Node(5

    root2.left.right = Node(4

    root2.right.left = Node(6

    root2.right.right = Node(7

  

    if (isSame(root1, root2)):

        print("Same"

    else:

        print("Not Same")

          
# Этот код предоставлен pranchalK

C #

// C # программа для проверки, если два листа обхода
// двух бинарных деревьев одинаковы или нет

using System;

using System.Collections.Generic;

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

    public Node(int x)

    {

        data = x;

        left = right = null;

    }

    public virtual bool Leaf

    {

        get

        {

            return (left == null && right == null);

        }

    }

}

  

class GFG

{
// Возвращает true для обхода листа
// два дерева одинаковы, иначе ложь

public static bool isSame(Node root1, Node root2)

{

    // Создать пустые стеки. Эти стеки

    // будем использовать для итеративного

    // обходы.

    Stack<Node> s1 = new Stack<Node>();

    Stack<Node> s2 = new Stack<Node>();

  

    s1.Push(root1);

    s2.Push(root2);

  

    // Цикл до двух стеков

    // не пусто

    while (s1.Count > 0 || s2.Count > 0)

    {

        // Если один из стеков пуст, значит другой

        // в стеке есть дополнительные листья, поэтому возвращаем false

        if (s1.Count == 0 || s2.Count == 0)

        {

            return false;

        }

  

        Node temp1 = s1.Pop();

        while (temp1 != null && !temp1.Leaf)

        {

            // Нажать правую и левую дочерние элементы temp1.

            // Обратите внимание, что правый потомок вставлен

            // перед тем как уйти

            if (temp1.right != null)

            {

                s1.Push(temp1.right);

            }

            if (temp1.left != null)

            {

                s1.Push(temp1.left);

            }

            temp1 = s1.Pop();

        }

  

        // то же самое для tree2

        Node temp2 = s2.Pop();

        while (temp2 != null && !temp2.Leaf)

        {

            if (temp2.right != null)

            {

                s2.Push(temp2.right);

            }

            if (temp2.left != null)

            {

                s2.Push(temp2.left);

            }

            temp2 = s2.Pop();

        }

  

        // Если один равен нулю, а другой нет,

        // затем возвращаем false

        if (temp1 == null && temp2 != null)

        {

            return false;

        }

        if (temp1 != null && temp2 == null)

        {

            return false;

        }

  

        // Если оба не нулевые и данные

        // не то же самое, возвращаем ложь

        if (temp1 != null && temp2 != null)

        {

            if (temp1.data != temp2.data)

            {

            return false;

            }

        }

    }

  

    // Если управление достигает этой точки,

    // все листья совпадают

    return true;

}

  
// Код драйвера

public static void Main(string[] args)

{

    // Давайте создадим деревья в примере выше 1

    Node root1 = new Node(1);

    root1.left = new Node(2);

    root1.right = new Node(3);

    root1.left.left = new Node(4);

    root1.right.left = new Node(6);

    root1.right.right = new Node(7);

  

    Node root2 = new Node(0);

    root2.left = new Node(1);

    root2.right = new Node(5);

    root2.left.right = new Node(4);

    root2.right.left = new Node(6);

    root2.right.right = new Node(7);

  

    if (isSame(root1, root2))

    {

        Console.WriteLine("Same");

    }

    else

    {

        Console.WriteLine("Not Same");

    }

}
}

  
// Этот код предоставлен Shrikant13

Выход:

Same

Эта статья предоставлена Кумаром Гауравом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проверьте, является ли обход двух бинарных деревьев одним и тем же?

0.00 (0%) 0 votes