Vidhya
BAN USERMy O(N) solution. But I am using extra O(N) space too.
class Tree{
List<Integer> children;
Tree(){
children = new ArrayList<Integer>();
}
}
public void cutSubTree(Node [] node , int ind){
int n = node.length;
Tree tree[] = new Tree[n];
for (int i=0; i<n; i++){
tree[i] = new Tree();
}
for (int i =0; i<n; i++){
if (node[i].pI != -1)
tree[node[i].pI].children.add(i);
}
printValids(node);
makeInvalid(tree, node, ind);
printValids(node);
}
public void makeInvalid(Tree[] tree, Node[] node, int ind){
node[ind].isValid = false;
for (int i: tree[ind].children)
makeInvalid(tree, node, i);
}
public void printValids(Node[] node){
for (int i =0; i<node.length; i++){
if (node[i].isValid){
System.out.print(node[i].node + " ");
}
}
System.out.println();
}
- Vidhya May 15, 2017