Tuesday, March 1, 2022

Are Trees Mirror In Shape

I/P:

12 10 20 -1 30 50 -1 60 -1 -1 40 -1 -1 12 100 200 -1 300 500 -1 600 -1 -1 400 -1 -1


O/P: true

1. Compare the size of parent node

2. Compare the size of children of Node_1's first child and Node_2's last child

package pep.Day30;

import java.io.*;
import java.util.*;

public class Are_Trees_Mirror_In_Shape {
private static class Node {
int data;
ArrayList<Node> children = new ArrayList<>();
}

public static void display(Node node) {
String str = node.data + " -> ";
for (Node child : node.children) {
str += child.data + ", ";
}
str += ".";
System.out.println(str);

for (Node child : node.children) {
display(child);
}
}

public static Node construct(int[] arr) {
Node root = null;

Stack<Node> st = new Stack<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == -1) {
st.pop();
} else {
Node t = new Node();
t.data = arr[i];

if (st.size() > 0) {
st.peek().children.add(t);
} else {
root = t;
}

st.push(t);
}
}

return root;
}

public static boolean areMirror(Node n1, Node n2) {
if (n1.children.size() != n2.children.size())
return false;

for (int i = 0; i < n1.children.size(); i++) {
Node c1 = n1.children.get(i);
Node c2 = n2.children.get(n2.children.size() - 1 - i);
boolean bool = areMirror(c1, c2);
if (!bool)
return false;
}
return true;
}

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n1 = Integer.parseInt(br.readLine());
int[] arr1 = new int[n1];
String[] values1 = br.readLine().split(" ");
for (int i = 0; i < n1; i++) {
arr1[i] = Integer.parseInt(values1[i]);
}
Node root1 = construct(arr1);

int n2 = Integer.parseInt(br.readLine());
int[] arr2 = new int[n2];
String[] values2 = br.readLine().split(" ");
for (int i = 0; i < n2; i++) {
arr2[i] = Integer.parseInt(values2[i]);
}
Node root2 = construct(arr2);

boolean mirror = areMirror(root1, root2);
System.out.println(mirror);
}

}




No comments:

Post a Comment

Diagonal Traversal

 eg.  1       2       3       4 5      6       7       8 9    10    11     12 13  14   15    16 Output: 1 6 11 16 2 7 12 3 8 4  Approach:...