# Java Solution, similar to BFS Topological sort

• We delete nodes layer by layer: for each round,we delete the nodes whose outdegree=0, and update their parent's outdegree. It's very similar similar with what we did in Topological Sort(in TopoSort,each round we delete those whose indegree=1 and iterate)

Use two HashMap, one for recording the outdegree of each TreeNode, and one for recording the parent of each TreeNode; first traverse the tree and load the maps, and then put those whose outdegree=0 into a Deque and iterate until running out of nodes.

``````import java.util.LinkedHashMap;

public class Solution{
public List<List<Integer>> findLeaves(TreeNode root){
List<List<Integer>> res=new ArrayList<>();

//record outdegree of every node
//record parent of every node
HashMap<TreeNode,TreeNode> parent=new HashMap<TreeNode,TreeNode>();

for(TreeNode node:outdegree.keySet()){
if(outdegree.get(node)==0){
q.offer(node);
}
}
while(!q.isEmpty()){
int size=q.size();
List<Integer> tmp=new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode t=q.poll();
if(t!=root){
outdegree.put(parent.get(t),outdegree.get(parent.get(t))-1);
if(outdegree.get(parent.get(t))==0){
q.offer(parent.get(t));
}
}
}
}

return res;
}

public void loadMap(TreeNode root,HashMap<TreeNode,Integer> outdegree,HashMap<TreeNode,TreeNode> parent){
if(root==null){
return;
}
if(root.left==null&&root.right==null){
outdegree.put(root,0);
return;
}

int degree=0;
if(root.left!=null){
degree++;
parent.put(root.left,root);
}
if(root.right!=null){
degree++;
parent.put(root.right,root);
}
outdegree.put(root,degree);