Java Solution, similar to BFS Topological sort


  • 3

    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);
    }
    

    }


  • 0
    J

    Is this time complexity O(N)? I think in the last section to process node with outdegree as 0, it actually still visits each node once.


Log in to reply
 

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