Skip to content

Instantly share code, notes, and snippets.

@jiananlu
Last active August 29, 2015 14:16
Show Gist options
  • Save jiananlu/7d456d7f224255166a51 to your computer and use it in GitHub Desktop.
Save jiananlu/7d456d7f224255166a51 to your computer and use it in GitHub Desktop.
class KArayTree {
private Node bfs(List<Node> preOrder, int k){
Node root = preOrder.get(0);
Deque<Node> q = new ArrayDeque<>();
q.addLast(root);
int index=1;
while(!q.isEmpty()){
Node p = q.removeFirst();
p.deleteAllChildren();
for(int i=0;i<k;i++){
if(index>=preOrder.size())
return root;
p.addChild(preOrder.get(index));
q.addLast(preOrder.get(index));
index++;
}
}
return root;
}
private List<Node> preOrder(Node root){
List<Node> res = new ArrayList<>();
dfs(root, res);
return res;
}
private void dfs(Node root, List<Node> res){
if(root==null)
return;
res.add(root);
for(Node c: root.getAllChildren())
dfs(c, res);
}
public Node completeKAryTree(Node root, int k){
if(root==null)
return null;
return bfs(preOrder(root), k);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment