You are viewing a single comment's thread. Return to all comments →
My Java 8 solution
class Node { private Integer value; private Node left; private Node right; public Node (Integer value){ this.value = value; } public Integer getValue(){ return value; } public Node getLeft(){ return left; } public Node getRight(){ return right; }; public void setValue(Integer value){ this.value = value; } public void setLeft(Node left){ this.left = left; } public void setRight(Node right){ this.right = right; }; public String toString(){ return String.format("Node: %s Left: %s Right: %s", this.value, this.left==null? "-1": this.left.getValue(), this.right==null? "-1": this.right.getValue() ); } public void swapNodes() { Node temp = this.left; this.left = this.right; this.right = temp; } } public List<List<Integer>> swapNodes(List<List<Integer>> indexes, List<Integer> queries) { List<List<Integer>> result = new ArrayList<>(); List<List<Node>> treeNodes = getTree(indexes); System.out.println("---------Original---------"); treeNodes.forEach(level -> { System.out.println("---------" + treeNodes.size()); level.forEach(node -> System.out.println(node)); }); List<Integer> inorderQuery; System.out.println("---------SWAP---------"); for (Integer query : queries) { inorderQuery = new ArrayList<>(); swap(query, treeNodes); treeNodes.forEach(level -> { System.out.println("---------"); level.forEach(node -> System.out.println(node)); }); getInOrderTraversal(treeNodes.get(0).get(0), inorderQuery); result.add(new ArrayList<>(inorderQuery)); } return result; } private List<List<Node>> getTree(List<List<Integer>> indexes){ Node root = new Node(1); List<List<Node>> treeNodes = new ArrayList<>(); List<Node> levelNodes = new ArrayList<>(); Queue<Node> levelQueue = new ArrayDeque<>(); levelQueue.add(root); Queue<Node> childDQueue = new ArrayDeque<>(); Node actualNode; for (List<Integer> nodes : indexes) { actualNode = levelQueue.poll(); levelNodes.add(actualNode); if(nodes.get(0)!=-1){ actualNode.setLeft(new Node(nodes.get(0))); childDQueue.add(actualNode.getLeft()); } if(nodes.get(1)!=-1){ actualNode.setRight(new Node(nodes.get(1))); childDQueue.add(actualNode.getRight()); } if(levelQueue.isEmpty()){ treeNodes.add(new ArrayList<Node>(levelNodes)); levelNodes = new ArrayList<>(); levelQueue = new ArrayDeque<>(childDQueue); childDQueue = new ArrayDeque<>(); } } return treeNodes; } private void swap(Integer query, List<List<Node>> treeNodes){ int multipleLevel = query; while (multipleLevel < treeNodes.size()) { treeNodes.get(multipleLevel-1).forEach(Node::swapNodes); multipleLevel += query; } } private void getInOrderTraversal(Node node, List<Integer> inOrderNodes){ if(node.left!=null) { getInOrderTraversal(node.left, inOrderNodes); } inOrderNodes.add(node.value); if(node.right!=null){ getInOrderTraversal(node.right, inOrderNodes); } } }
Seems like cookies are disabled on this browser, please enable them to open this website
Swap Nodes [Algo]
You are viewing a single comment's thread. Return to all comments →
My Java 8 solution