//https://www.hackerrank.com/challenges/swap-nodes-algo/problem
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Node {
public int data;
public int height;
public Node left;
public Node right;
public Node (int data) {
this.data = data;
}
public Node (int data, int height) {
this.data = data;
this.height = height;
}
}
class Tree {
public Node root;
public void Insert(int data) {
if (root == null) {
root = new Node(data, 1);
} else {
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
if (n != null && n.data != -1) { // check for the null nodes!
if (n.left != null) {
q.add(n.left);
} else {
Node insert = new Node(data, n.height + 1);
n.left = insert;
return;
}
if (n.right != null) {
q.add(n.right);
} else {
Node insert = new Node(data, n.height + 1);
n.right = insert;
return;
}
}
}
}
}
public void printPreOrder(Node node) {
if (node != null) {
System.out.println(node.height + ": " + node.data);
printPreOrder(node.left);
printPreOrder(node.right);
}
}
public void printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
if (node.data != -1)
System.out.print(node.data + " ");
printInOrder(node.right);
}
}
public void swap(int k) {
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
if (n != null)
{
if (n.height == k) {
//Perform swap
Node temp = n.right;
n.right = n.left;
n.left = temp;
} else {
q.add(n.left);
q.add(n.right);
}
}
}
printInOrder(root);
System.out.println();
}
public Tree(Node root) {
root.height = 1; // just in case
this.root = root;
}
public Tree() {
this.root = null;
}
}
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Tree t = new Tree();
t.Insert(1);
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i < N; i++) {
int left = scanner.nextInt();
int right = scanner.nextInt();
t.Insert(left);
t.Insert(right);
}
int T = scanner.nextInt();
for (int i = 0; i < T; i++) {
int k = scanner.nextInt();
t.swap(k);
}
}
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.