Java BFS Solution using Queue/Marker - O(n)


  • 0
    1

    public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        if(root == null) return list;
        
        List<Integer> sublist = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode node, marker = new TreeNode(0);
        q.add(root);
        q.add(marker);
       
        while(!q.isEmpty()){
            
            node = q.poll();
           
            if(node.equals(marker)){
               
                list.add(new ArrayList(sublist));
                sublist.clear();
                
                if(!q.isEmpty()){
                    q.add(marker);
                }
                
            }
            
            if(!node.equals(marker)) sublist.add(node.val);
            if(node.left != null) q.add(node.left);
            if(node.right != null) q.add(node.right);
        }
        
        return list;
    }
    

    }


Log in to reply
 

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