Java Solution, similar to BFS Topological sort


  • 2

    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
    	HashMap<TreeNode,Integer> outdegree=new LinkedHashMap<TreeNode,Integer>();
    	//record parent of every node
    	HashMap<TreeNode,TreeNode> parent=new HashMap<TreeNode,TreeNode>();
    	loadMap(root,outdegree,parent);
    
    	Deque<TreeNode> q=new LinkedList<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();
    			tmp.add(t.val);
    			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));
    				}
    			}
    		}
    		res.add(tmp);
    	}
    
    	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);
    	
    	loadMap(root.left,outdegree,parent);
    	loadMap(root.right,outdegree,parent);
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.