Dado un árbol binario , compruebe si es un espejo de sí mismo.
Ejemplos:
Input:
5
/ \
3 3
/ \ / \
8 9 9 8
Output: Symmetric
Input:
5
/ \
8 7
\ \
4 3
Output: Not Symmetric
Enfoque: La idea es atravesar el árbol usando Morris Traversal y Reverse Morris Traversal para recorrer el árbol binario dado y en cada paso verificar que los datos del Node actual sean iguales en ambos recorridos. Si en algún paso los datos de los Nodes son diferentes. Entonces, el árbol dado no es un árbol binario simétrico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to check
// if Tree is symmetric or not
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
Node* left;
Node* right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
// Function to check if the given
// binary tree is Symmetric or not
bool isSymmetric(struct Node* root)
{
Node *curr1 = root, *curr2 = root;
// Loop to traverse the tree in
// Morris Traversal and
// Reverse Morris Traversal
while (curr1 != NULL
&& curr2 != NULL) {
if (curr1->left == NULL
&& curr2->right == NULL) {
if (curr1->data != curr2->data)
return false;
curr1 = curr1->right;
curr2 = curr2->left;
}
else if (curr1->left != NULL
&& curr2->right != NULL) {
Node* pre1 = curr1->left;
Node* pre2 = curr2->right;
while (pre1->right != NULL
&& pre1->right != curr1
&& pre2->left != NULL
&& pre2->left != curr2) {
pre1 = pre1->right;
pre2 = pre2->left;
}
if (pre1->right == NULL
&& pre2->left == NULL) {
// Here, we are threading the Node
pre1->right = curr1;
pre2->left = curr2;
curr1 = curr1->left;
curr2 = curr2->right;
}
else if (pre1->right == curr1
&& pre2->left == curr2) {
// Unthreading the nodes
pre1->right = NULL;
pre2->left = NULL;
if (curr1->data != curr2->data)
return false;
curr1 = curr1->right;
curr2 = curr2->left;
}
else
return false;
}
else
return false;
}
if (curr1 != curr2)
return false;
return true;
}
// Driver Code
int main()
{
/*
5
/ \
3 3
/ \ / \
8 9 9 8 */
// Creation of Binary tree
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(3);
root->left->left = new Node(8);
root->left->right = new Node(9);
root->right->left = new Node(9);
root->right->right = new Node(8);
if (isSymmetric(root))
cout << "Symmetric";
else
cout << "Not Symmetric";
return 0;
}
Java
// Java implementation to check
// if Tree is symmetric or not
class GFG{
// A Binary Tree Node
static class Node
{
int data;
Node left;
Node right;
Node(int val)
{
data = val;
left = right = null;
}
};
// Function to check if the given
// binary tree is Symmetric or not
static boolean isSymmetric(Node root)
{
Node curr1 = root, curr2 = root;
// Loop to traverse the tree in
// Morris Traversal and
// Reverse Morris Traversal
while (curr1 != null &&
curr2 != null)
{
if (curr1.left == null &&
curr2.right == null)
{
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else if (curr1.left != null &&
curr2.right != null)
{
Node pre1 = curr1.left;
Node pre2 = curr2.right;
while (pre1.right != null &&
pre1.right != curr1 &&
pre2.left != null &&
pre2.left != curr2)
{
pre1 = pre1.right;
pre2 = pre2.left;
}
if (pre1.right == null &&
pre2.left == null)
{
// Here, we are threading the Node
pre1.right = curr1;
pre2.left = curr2;
curr1 = curr1.left;
curr2 = curr2.right;
}
else if (pre1.right == curr1 &&
pre2.left == curr2)
{
// Unthreading the nodes
pre1.right = null;
pre2.left = null;
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else
return false;
}
else
return false;
}
if (curr1 != curr2)
return false;
return true;
}
// Driver Code
public static void main(String[] args)
{
/*
5
/ \
3 3
/ \ / \
8 9 9 8 */
// Creation of Binary tree
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(3);
root.left.left = new Node(8);
root.left.right = new Node(9);
root.right.left = new Node(9);
root.right.right = new Node(8);
if (isSymmetric(root))
System.out.print("Symmetric");
else
System.out.print("Not Symmetric");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to check
# if Tree is symmetric or not
# A Binary Tree Node
class Node:
def __init__(self, val):
self.data = val
self.left = self.right = None
# Function to check if the given
# binary tree is Symmetric or not
def isSymmetric(root):
curr1 = root
curr2 = root
# Loop to traverse the tree in
# Morris Traversal and
# Reverse Morris Traversal
while curr1 != None and curr2 != None:
if (curr1.left == None and
curr2.right == None):
if curr1.data != curr2.data:
return False
curr1 = curr1.right
curr2 = curr2.left
elif curr1 != None and curr2 != None:
pre1 = curr1.left
pre2 = curr2.right
while (pre1.right != None and
pre1.right != curr1 and
pre2.left != None and
pre2.left != curr2):
pre1 = pre1.right
pre2 = pre2.left
if pre1.right == None and pre2.left == None:
# Here, we are threading the Node
pre1.right = curr1
pre2.left = curr2
curr1 = curr1.left
curr2 = curr2.right
elif (pre1.right == curr1 and
pre2.left == curr2):
# Unthreading the nodes
pre1.right = None
pre2.left = None
if curr1.data != curr2.data:
return False
curr1 = curr1.right
curr2 = curr2.left
else:
return False
else:
return False
if curr1 != curr2:
return False
return True
# Driver code
def main():
#
# 5
# / \
# 3 3
# / \ / \
#8 9 9 8
# Creation of Binary tree
root = Node(5)
root.left = Node(3)
root.right = Node(3)
root.left.left = Node(8)
root.left.right = Node(9)
root.right.left = Node(9)
root.right.right = Node(8)
if isSymmetric(root):
print("Symmetric")
else:
print("Not Symmetric")
main()
# This code is contributed by Stuti Pathak
C#
// C# implementation to check
// if Tree is symmetric or not
using System;
class GFG{
// A Binary Tree Node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int val)
{
data = val;
left = right = null;
}
};
// Function to check if the given
// binary tree is Symmetric or not
static bool isSymmetric(Node root)
{
Node curr1 = root, curr2 = root;
// Loop to traverse the tree in
// Morris Traversal and
// Reverse Morris Traversal
while (curr1 != null &&
curr2 != null)
{
if (curr1.left == null &&
curr2.right == null)
{
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else if (curr1.left != null &&
curr2.right != null)
{
Node pre1 = curr1.left;
Node pre2 = curr2.right;
while (pre1.right != null &&
pre1.right != curr1 &&
pre2.left != null &&
pre2.left != curr2)
{
pre1 = pre1.right;
pre2 = pre2.left;
}
if (pre1.right == null &&
pre2.left == null)
{
// Here, we are threading the Node
pre1.right = curr1;
pre2.left = curr2;
curr1 = curr1.left;
curr2 = curr2.right;
}
else if (pre1.right == curr1 &&
pre2.left == curr2)
{
// Unthreading the nodes
pre1.right = null;
pre2.left = null;
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else
return false;
}
else
return false;
}
if (curr1 != curr2)
return false;
return true;
}
// Driver Code
public static void Main(String[] args)
{
/*
5
/ \
3 3
/ \ / \
8 9 9 8 */
// Creation of Binary tree
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(3);
root.left.left = new Node(8);
root.left.right = new Node(9);
root.right.left = new Node(9);
root.right.right = new Node(8);
if (isSymmetric(root))
Console.Write("Symmetric");
else
Console.Write("Not Symmetric");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to check
// if Tree is symmetric or not
// A Binary Tree Node
class Node
{
constructor(val) {
this.left = null;
this.right = null;
this.data = val;
}
}
// Function to check if the given
// binary tree is Symmetric or not
function isSymmetric(root)
{
let curr1 = root, curr2 = root;
// Loop to traverse the tree in
// Morris Traversal and
// Reverse Morris Traversal
while (curr1 != null &&
curr2 != null)
{
if (curr1.left == null &&
curr2.right == null)
{
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else if (curr1.left != null &&
curr2.right != null)
{
let pre1 = curr1.left;
let pre2 = curr2.right;
while (pre1.right != null &&
pre1.right != curr1 &&
pre2.left != null &&
pre2.left != curr2)
{
pre1 = pre1.right;
pre2 = pre2.left;
}
if (pre1.right == null &&
pre2.left == null)
{
// Here, we are threading the Node
pre1.right = curr1;
pre2.left = curr2;
curr1 = curr1.left;
curr2 = curr2.right;
}
else if (pre1.right == curr1 &&
pre2.left == curr2)
{
// Unthreading the nodes
pre1.right = null;
pre2.left = null;
if (curr1.data != curr2.data)
return false;
curr1 = curr1.right;
curr2 = curr2.left;
}
else
return false;
}
else
return false;
}
if (curr1 != curr2)
return false;
return true;
}
/*
5
/ \
3 3
/ \ / \
8 9 9 8 */
// Creation of Binary tree
let root = new Node(5);
root.left = new Node(3);
root.right = new Node(3);
root.left.left = new Node(8);
root.left.right = new Node(9);
root.right.left = new Node(9);
root.right.right = new Node(8);
if (isSymmetric(root))
document.write("Symmetric");
else
document.write("Not Symmetric");
</script>
Producción:
Symmetric
Complejidad de tiempo: dado que cada borde del árbol se recorre como máximo dos veces exactamente como en el caso del recorrido de Morris y, en el peor de los casos, se crea y elimina la misma cantidad de bordes adicionales (como el árbol de entrada). Por lo tanto, la complejidad temporal de este enfoque es O(N) .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por infinity9online y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA