Java Solution using BFS and decorating TreeNode with 'level' attribute


  • 1
    P
    public class Solution {
      public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> list = new ArrayList<>();
    	if(root == null) return list;
    	
    	Queue<TreeNodeWithLevel> queue = new LinkedList<>();
    	int level = 0;
    	TreeNodeWithLevel rootNode = new TreeNodeWithLevel(root, level);
    	queue.add(rootNode);
    	
    	while(!queue.isEmpty()){
    		TreeNodeWithLevel node = queue.poll();
    		List<Integer> levelList;
    		if(list.size() == node.level){
    			levelList = new ArrayList<>();
    			list.add(levelList);
    		}
    		else
    			levelList = list.get(node.level);
    
    		levelList.add(node.node.val);
    		
    		if(node.node.left != null){
    			TreeNodeWithLevel left = new TreeNodeWithLevel(node.node.left, node.level+1);
    			queue.add(left);
    		}
    		
    		if(node.node.right != null){
    			TreeNodeWithLevel right = new TreeNodeWithLevel(node.node.right, node.level+1);
    			queue.add(right);
    		}
    	}
    	
    	return list;
    }
    
    public class TreeNodeWithLevel{
    	TreeNode node;
    	int level;
    	
    	public TreeNodeWithLevel(TreeNode node, int level){
    		this.node = node;
    		this.level = level;
    	}
    }
    

    }


Log in to reply
 

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