Рубрики

Найти первые не совпадающие листья в двух бинарных деревьях

Учитывая два двоичных дерева, найдите первые листья двух деревьев, которые не совпадают. Если нет несоответствующих листьев, ничего не печатать.

Примеры:

Input : First Tree
          5
        /   \
       2     7
     /   \
   10     11

      Second Tree   
          6
       /    \
     10     15

Output : 11 15
If we consider leaves of two trees in order,
we can see that 11 and 15 are the first leaves 
that do not match.

Способ 1 (простой):
Сделайте Inorder обход обоих деревьев один за другим, сохраните листья обоих деревьев в двух разных списках. Наконец, найдите первые значения, которые отличаются в обоих списках. Временная сложность составляет O (n1 + n2), где n1 и n2 — количество узлов в двух деревьях. Требуемое дополнительное пространство составляет O (n1 + n2).

Метод 2 (Эффективный)
Это решение требует вспомогательного пространства как O (h1 + h2), где h1 и h2 — высоты деревьев. Мы выполняем итеративный предварительный обход обоих деревьев одновременно, используя стеки. Мы поддерживаем стек для каждого дерева. Для каждого дерева продолжайте помещать узлы в стеке, пока верхний узел не станет листовым узлом. Сравните два верхних узла в стеке. Если они равны, сделайте дальнейший обход, иначе вернитесь.

C ++

// C ++ программа для поиска первых листьев, которые
// не то же самое.
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева

struct Node

{

    int data;

    Node *left,  *right;

};

  
// Служебный метод для создания нового узла

Node *newNode(int x)

{

    Node * temp = new Node;

    temp->data = x;

    temp->left = temp->right = NULL;

    return temp;

}

  

bool isLeaf(Node * t)

{

    return ((t->left == NULL) && (t->right == NULL));

}

  
// Печатает первый несовпадающий листовой узел в
// два дерева, если оно существует, иначе ничего не печатает.

void findFirstUnmatch(Node *root1, Node *root2)

{

    // Если какое-либо дерево пусто

    if (root1 == NULL || root2 == NULL)

      return;

  

    // Создаем два стека для обхода предзаказа

    stack<Node*> s1, s2;

    s1.push(root1);

    s2.push(root2);

  

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

    {

        // Если обход одного дерева окончен

        // и другое дерево все еще имеет узлы.

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

           return;

  

        // Делаем итеративный обход первого дерева

        // и найти первый ведущий узел в нем как «temp1»

        Node *temp1 = s1.top();

        s1.pop();

        while (temp1 && !isLeaf(temp1))

        {

            // нажимаем вправо на ребенка, чтобы

            // левый ребенок появляется первым во время всплытия.

            s1.push(temp1->right);

            s1.push(temp1->left);

            temp1 = s1.top();

            s1.pop();

        }

  

        // Делаем итеративный обход второго дерева

        // и найти первый ведущий узел в нем как "temp2"

        Node * temp2 = s2.top();

        s2.pop();

        while (temp2 && !isLeaf(temp2))

        {

            s2.push(temp2->right);

            s2.push(temp2->left);

            temp2 = s2.top();

            s2.pop();

        }

  

        // Если мы нашли листья на обоих деревьях

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

        {

            if (temp1->data != temp2->data )

            {

                cout << "First non matching leaves : "

                     << temp1->data <<"  "<< temp2->data

                     << endl;

                return;

            }

        }

    }

}

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

int main()

{

    struct Node *root1 = newNode(5);

    root1->left = newNode(2);

    root1->right = newNode(7);

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

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

  

    struct Node * root2 = newNode(6);

    root2->left = newNode(10);

    root2->right = newNode(15);

  

    findFirstUnmatch(root1,root2);

  

    return 0;

}

Джава

// Java-программа для поиска первых листьев
// не то же самое.

import java.util.*;

class GfG {

  
// Узел дерева

static class Node 

    int data; 

    Node left, right; 

}

  
// Служебный метод для создания нового узла

static Node newNode(int x) 

    Node temp = new Node(); 

    temp.data = x; 

    temp.left = null;

    temp.right = null

    return temp; 

  

static boolean isLeaf(Node t) 

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

  
// Печатает первый несовпадающий листовой узел в
// два дерева, если оно существует, иначе ничего не печатает.

static void findFirstUnmatch(Node root1, Node root2) 

    // Если какое-либо дерево пусто

    if (root1 == null || root2 == null

    return

  

    // Создаем два стека для обхода предзаказа

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

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

    s1.push(root1); 

    s2.push(root2); 

  

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

    

        // Если обход одного дерева окончен

        // и другое дерево все еще имеет узлы.

        if (s1.isEmpty() || s2.isEmpty() ) 

        return

  

        // Делаем итеративный обход первого дерева

        // и найти первый ведущий узел в нем как «temp1»

        Node temp1 = s1.peek(); 

        s1.pop(); 

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

        

            // нажимаем вправо на ребенка, чтобы

            // левый ребенок появляется первым во время всплытия.

            s1.push(temp1.right); 

            s1.push(temp1.left); 

            temp1 = s1.peek(); 

            s1.pop(); 

        

  

        // Делаем итеративный обход второго дерева

        // и найти первый ведущий узел в нем как "temp2"

        Node temp2 = s2.peek(); 

        s2.pop(); 

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

        

            s2.push(temp2.right); 

            s2.push(temp2.left); 

            temp2 = s2.peek(); 

            s2.pop(); 

        

  

        // Если мы нашли листья на обоих деревьях

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

        

            if (temp1.data != temp2.data ) 

            

                System.out.println(temp1.data+" "+temp2.data); 

                return

            

        

    

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

public static void main(String[] args) 

    Node root1 = newNode(5); 

    root1.left = newNode(2); 

    root1.right = newNode(7); 

    root1.left.left = newNode(10); 

    root1.left.right = newNode(11); 

  

    Node root2 = newNode(6); 

    root2.left = newNode(10); 

    root2.right = newNode(15); 

  

    findFirstUnmatch(root1,root2); 

  

python3

# Python3 программа для поиска первых листьев
# это не одно и то же

  
# Tree Node
# Сервисная функция для создания
# Новый узел дерева

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          

def isLeaf(t): 

  

    return ((t.left == None) and 

            (t.right == None)) 

  
# Печатает первый не соответствующий листовой узел в
# два дерева, если оно существует, иначе ничего не печатает.

def findFirstUnmatch(root1, root2) :

  

    # Если любое дерево пусто

    if (root1 == None or root2 == None) :

        return

  

    # Создать два стека для предварительного заказа

    # обходы

    s1 = []

    s2 = [] 

    s1.insert(0, root1) 

    s2.insert(0, root2) 

  

    while (len(s1) or len(s2)) :

      

        # Если обход одного дерева окончен

        # и другое дерево все еще имеет узлы.

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

            return

  

        # Выполнить итеративный обход первого

        # дерево и найти первый ведущий узел

        # в нем как "temp1"

        temp1 = s1[0

        s1.pop(0

        while (temp1 and not isLeaf(temp1)) :

          

            # нажимаем вправо на ребенка, чтобы

            # левый ребенок появляется первым во время сования.

            s1.insert(0, temp1.right) 

            s1.insert(0, temp1.left) 

            temp1 = s1[0

            s1.pop(0

          

        # Выполнить итеративный обход второго дерева

        # и найдите первый ведущий узел в нем как "temp2"

        temp2 = s2[0]

        s2.pop(0

        while (temp2 and not isLeaf(temp2)) :

          

            s2.insert(0, temp2.right) 

            s2.insert(0, temp2.left) 

            temp2 = s2[0]

            s2.pop(0

          

        # Если мы нашли листья на обоих деревьях

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

          

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

              

                print("First non matching leaves :",

                        temp1.data, "", temp2.data ) 

                return

  
Код водителя

if __name__ == '__main__':

    root1 = newNode(5

    root1.left = newNode(2

    root1.right = newNode(7

    root1.left.left = newNode(10

    root1.left.right = newNode(11

  

    root2 = newNode(6

    root2.left = newNode(10

    root2.right = newNode(15

  

    findFirstUnmatch(root1,root2)

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

C #

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

using System;

using System.Collections.Generic;

  

class GfG 

{

  

    // Узел дерева

    public class Node 

    

        public int data; 

        public Node left, right; 

    }

  

    // Служебный метод для создания нового узла

    static Node newNode(int x) 

    

        Node temp = new Node(); 

        temp.data = x; 

        temp.left = null;

        temp.right = null

        return temp; 

    

  

    static bool isLeaf(Node t) 

    

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

    

  

    // Печатает первый несовпадающий листовой узел в

    // два дерева, если оно существует, иначе ничего не печатает.

    static void findFirstUnmatch(Node root1, Node root2) 

    

        // Если какое-либо дерево пусто

        if (root1 == null || root2 == null

        return

  

        // Создаем два стека для обхода предзаказа

        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) 

        

            // Если обход одного дерева окончен

            // и другое дерево все еще имеет узлы.

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

            return

  

            // Делаем итеративный обход первого дерева

            // и найти первый ведущий узел в нем как «temp1»

            Node temp1 = s1.Peek(); 

            s1.Pop(); 

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

            

                // нажимаем вправо на ребенка, чтобы

                // левый ребенок появляется первым во время всплытия.

                s1.Push(temp1.right); 

                s1.Push(temp1.left); 

                temp1 = s1.Peek(); 

                s1.Pop(); 

            

  

            // Делаем итеративный обход второго дерева

            // и найти первый ведущий узел в нем как "temp2"

            Node temp2 = s2.Peek(); 

            s2.Pop(); 

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

            

                s2.Push(temp2.right); 

                s2.Push(temp2.left); 

                temp2 = s2.Peek(); 

                s2.Pop(); 

            

  

            // Если мы нашли листья на обоих деревьях

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

            

                if (temp1.data != temp2.data ) 

                

                    Console.WriteLine(temp1.data + " " + temp2.data); 

                    return

                

            

        

    

  

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

    public static void Main(String[] args) 

    

        Node root1 = newNode(5); 

        root1.left = newNode(2); 

        root1.right = newNode(7); 

        root1.left.left = newNode(10); 

        root1.left.right = newNode(11); 

  

        Node root2 = newNode(6); 

        root2.left = newNode(10); 

        root2.right = newNode(15); 

  

        findFirstUnmatch(root1,root2); 

  

    

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


Выход:

First non matching leaves : 11  15

Ссылки:

Эта статья предоставлена Ekta Goel . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Найти первые не совпадающие листья в двух бинарных деревьях

0.00 (0%) 0 votes