Проверьте, являются ли два дерева зеркальными друг друга, используя обход порядка уровней
Опубликовано: 24 Января, 2022
Учитывая два бинарных дерева, задача состоит в том, чтобы проверить, являются ли два бинарных дерева зеркалом друг друга или нет.
Зеркало двоичного дерева: зеркало двоичного дерева T - это еще одно двоичное дерево M (T), в котором местами заменены левые и правые дочерние элементы всех нелистовых узлов.
Деревья на рисунке выше являются зеркалами друг друга.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Рекурсивное решение и итерационный метод с использованием обхода по порядку для проверки того, являются ли два двоичных дерева зеркалом друг друга, уже обсуждались. В этом посте обсуждалось решение, использующее обход порядка уровней.
Идея состоит в том, чтобы использовать очередь, в которой два узла обоих деревьев, которые необходимо проверить на равенство, присутствуют вместе. На каждом шаге обхода порядка уровней получите два узла из очереди, проверьте их равенство и затем вставьте следующие два дочерних узла этих узлов, которые необходимо проверить на равенство. На этапе вставки вставляются первый левый дочерний элемент первого узла дерева и правый дочерний элемент второго узла дерева. После этого вставляются правый дочерний элемент первого узла дерева и левый дочерний элемент второго узла дерева. Если на каком-либо этапе один узел имеет значение NULL, а другой - нет, то оба дерева не являются зеркалом друг друга.
Below is the implementation of above approach:
C++
// C++ implementation to check whether the two// binary tress are mirrors of each other or not#include <bits/stdc++.h>using namespace std; // Structure of a node in binary treestruct Node { int data; struct Node *left, *right;}; // Function to create and return// a new node for a binary treestruct Node* newNode(int data){ struct Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;} // Function to check whether the two binary trees// are mirrors of each other or notstring areMirrors(Node* a, Node* b){ // If both are NULL, then are mirror. if (a == NULL && b == NULL) return "Yes"; // If only one is NULL, then not // mirror. if (a == NULL || b == NULL) return "No"; queue<Node*> q; // Push root of both trees in queue. q.push(a); q.push(b); while (!q.empty()) { // Pop two elements of queue, to // get two nodes and check if they // are symmetric. a = q.front(); q.pop(); b = q.front(); q.pop(); // If data value of both nodes is // not same, then not mirror. if (a->data != b->data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not NULL. if (a->left && b->right) { q.push(a->left); q.push(b->right); } // If any one of the nodes is NULL and // other is not NULL, then not mirror. else if (a->left || b->right) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not NULL. if (a->right && b->left) { q.push(a->right); q.push(b->left); } // If any one of the nodes is NULL and // other is not NULL, then not mirror. else if (a->right || b->left) return "No"; } return "Yes";}// Driver Codeint main(){ // 1st binary tree formation /* 1 / 3 2 / 5 4 */ Node* root1 = newNode(1); root1->left = newNode(3); root1->right = newNode(2); root1->right->left = newNode(5); root1->right->right = newNode(4); // 2nd binary tree formation /* 1 / 2 3 / 4 5 */ Node* root2 = newNode(1); root2->left = newNode(2); root2->right = newNode(3); root2->left->left = newNode(4); root2->left->right = newNode(5); cout << areMirrors(root1, root2); return 0;} |
Java
// Java implementation to check whether the two// binary tress are mirrors of each other or notimport java.util.*; class GFG{ // Structure of a node in binary treestatic class Node { int data; Node left, right;}; // Function to create and return// a new node for a binary treestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;} // Function to check whether the two binary trees// are mirrors of each other or notstatic String areMirrors(Node a, Node b){ // If both are null, then are mirror. if (a == null && b == null) return "Yes"; // If only one is null, then not // mirror. if (a == null || b == null) return "No"; Queue<Node> q = new LinkedList<Node>(); // Push root of both trees in queue. q.add(a); q.add(b); while (q.size() > 0) { // remove two elements of queue, to // get two nodes and check if they // are symmetric. a = q.peek(); q.remove(); b = q.peek(); q.remove(); // If data value of both nodes is // not same, then not mirror. if (a.data != b.data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not null. if (a.left != null && b.right != null) { q.add(a.left); q.add(b.right); } // If any one of the nodes is null and // other is not null, then not mirror. else if (a.left != null || b.right != null) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not null. if (a.right != null && b.left != null) { q.add(a.right); q.add(b.left); } //If any one of the nodes is null and // other is not null, then not mirror. else if (a.right != null || b.left != null) return "No"; } return "Yes";} // Driver Codepublic static void main(String args[]){ // 1st binary tree formation /* 1 / 3 2 / 5 4 */ Node root1 = newNode(1); root1.left = newNode(3); root1.right = newNode(2); root1.right.left = newNode(5); root1.right.right = newNode(4); // 2nd binary tree formation /* 1 / 2 3 / 4 5 */ Node root2 = newNode(1); root2.left = newNode(2); root2.right = newNode(3); root2.left.left = newNode(4); root2.left.right = newNode(5); System.out.print(areMirrors(root1, root2));}} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to check whether the two # binary tress are mirrors of each other or not # Structure of a node in binary tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to check whether the two binary # trees are mirrors of each other or not def areMirrors(a, b): # If both are NULL, then are mirror. if a == None and b == None: return "Yes" # If only one is NULL, then not mirror. if a == None or b == None: return "No" q = [] # append root of both trees in queue. q.append(a) q.append(b) while len(q) > 0: # Pop two elements of queue, # to get two nodes and check # if they are symmetric. a = q.pop(0) b = q.pop(0) # If data value of both nodes is # not same, then not mirror. if a.data != b.data: return "No" # append left child of first tree node # and right child of second tree node # into queue if both are not NULL. if a.left and b.right: q.append(a.left) q.append(b.right) # If any one of the nodes is NULL and # other is not NULL, then not mirror. elif a.left or b.right: return "No" # Append right child of first tree node # and left child of second tree node # into queue if both are not NULL. if a.right and b.left: q.append(a.right) q.append(b.left) # If any one of the nodes is NULL and # other is not NULL, then not mirror. elif a.right or b.left: return "No" return "Yes" # Driver Code if __name__ == "__main__": # 1st binary tree formation root1 = Node(1) root1.left = Node(3) root1.right = Node(2) root1.right.left = Node(5) root1.right.right = Node(4) # 2nd binary tree formation root2 = Node(1) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) print(areMirrors(root1, root2)) # This code is contributed by Rituraj Jain |
C#
// C# implementation to check whether the two// binary tress are mirrors of each other or notusing System;using System.Collections.Generic; class GFG{ // Structure of a node in binary treepublic class Node { public int data; public Node left, right;}; // Function to create and return// a new node for a binary treestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;} // Function to check whether the two binary trees// are mirrors of each other or notstatic String areMirrors(Node a, Node b){ // If both are null, then are mirror. if (a == null && b == null) return "Yes"; // If only one is null, then not // mirror. if (a == null || b == null) return "No"; Queue<Node> q = new Queue<Node>(); РЕКОМЕНДУЕМЫЕ СТАТЬИ |