Easy to understand, simple java bottom up solution


  • 1
    H
    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
    		Map<Integer,List<Integer>> result = new HashMap();
    		getLeaves(root,result);
    		return new ArrayList(result.values());
        }
    
    	private int getLeaves(TreeNode root,Map<Integer,List<Integer>> result){
    	    if(root == null) return -1;
    		int left = getLeaves(root.left, result);
    		int right = getLeaves(root.right, result);
    		if(root.left == null && root.right == null){
    		    addToResult(result,0,root.val);
    		    return 1;
    		}else{
    		    int maxHeight = Math.max(left,right);
    		    addToResult(result, maxHeight,root.val);
    		    return maxHeight + 1;
    		}
    	}
    	
    	private void addToResult(Map<Integer,List<Integer>> result, int index, int value){
    	    List<Integer> list = result.get(index);
    	    if(list == null){
    	        list = new ArrayList();
    	        result.put(index,list);
    	    }
    	    list.add(value);
    	}
    }
    

    Used the height of a node as a hash. To calculate the hash, I used bottom up approach. When a leaf node is reached, inserted the node with hash value 0. While returning from a node, I returned current node height + 1, which would be used as a hash in the higher levels.


Log in to reply
 

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