Java solution with a queue used


  • 169
    S
    public class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
            
            if(root == null) return wrapList;
            
            queue.offer(root);
            while(!queue.isEmpty()){
                int levelNum = queue.size();
                List<Integer> subList = new LinkedList<Integer>();
                for(int i=0; i<levelNum; i++) {
                    if(queue.peek().left != null) queue.offer(queue.peek().left);
                    if(queue.peek().right != null) queue.offer(queue.peek().right);
                    subList.add(queue.poll().val);
                }
                wrapList.add(subList);
            }
            return wrapList;
        }
    }

  • 1
    G

    A very nice solution using BFS


  • 0
    C

    How are you not getting an infinite loop if you're never removing anything from the queue in your while loop?


  • 2
    E

    queue.poll() is removing the top item from the queue. Check out this link if it is still unclear: https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#poll--


  • 0
    G

    Why you keep use queue.offer(queue.peek().left) and queue.offer(queue.peek().right) to add items in this queue?


  • 0
    V

    offer method adds elements to the queue. So the code is essentially adding the left and right children of the current node to the queue if they are not equal to null.


  • 28
    M

    nice solution.but I think some code can be simplified
    edit a little

    List<List<Integer>> res = new ArrayList<>();  
    if (root == null) return res;  
    Queue<TreeNode> queue = new LinkedList<>();  
    queue.add(root);  
    while (!queue.isEmpty()) {  
      List<Integer> level = new ArrayList<>();  
      int cnt = queue.size();  
      for (int i = 0; i < cnt; i++) {  
        TreeNode node = queue.poll();  
        level.add(node.val);  
        if (node.left != null) {  
          queue.add(node.left);  
        }
        if (node.right != null) {  
          queue.add(node.right);  
        }  
      }  
      res.add(level);   
    }  
    return res;
    

  • 6
    P

    I did it without a Queue

    https://leetcode.com/discuss/94687/short-easy-java-code-level-order-using-preorder-o-1

    public class Solution {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            func(root,0);
            return returnList;
    
        }
        public void func(TreeNode root,int level)
        {
            if(root==null)
            {
                return;
            }
            //VISIT
            if(returnList.size() >= level+1)
            {
                List<Integer> l = returnList.get(level);
                l.add(root.val);
            }
            else
            {
    
                List<Integer> temp  = new ArrayList<Integer>();
                temp.add(root.val);
                returnList.add(level,temp);
            }
    
            //go left and right
            func(root.left,level+1);
            func(root.right,level+1);
        }
    }

  • 0

    I assume the running time is O(n), even though it has a nested loop. Any thoughts?


  • 0
    K
    This post is deleted!

  • 0
    M

    @chidong

    I think you're right. Every treenode will perform 2 operations, so the time complexity is O(2n)--->O(n).


  • 0
    B

    @cindy11 queue.poll() will take care of that!


  • 0
    S

    This is an cool alternative approach, but not necessarily better than recursion.

    Using recursion, there will be at most O(n) extra memory used while the result list is being built (thanks to the implicit recursive stack, representing a single path from the root at a time which at most gets to a leaf).

    This method keeps an entire level of nodes in memory (next level to process), which at the last level is n / 2, resulting in O(n) space.

    That said, it still doesn't change the final O(n) space complexity (required by the problem, for having to return nested lists containing exactly n elements).


  • 0
    W

    C++ version:

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> res;
            queue<TreeNode *> nodes;
            
            if (!root) {
                return res;
            }
    
            nodes.push(root);
            
            while (!nodes.empty()) {
                int level = nodes.size();
                vector<int> tmp;
                for (int i = 0; i < level; ++i) {
                    if (nodes.front()->left) {
                        nodes.push(nodes.front()->left);
                    }
                    if (nodes.front()->right) {
                        nodes.push(nodes.front()->right);
                    }
                    tmp.push_back(nodes.front()->val);
                    nodes.pop();
                }
                
                res.push_back(tmp);
            }
            
            return res;
        }
    };
    

  • 0
    S

    java breadth first traversal 2ms

    	private static List<List<Integer>> levelOrderTraversal(TreeNode root)
    	{
    		List<List<Integer>> levelOrderTraversal = new ArrayList<List<Integer>>();
    		List<Integer> currentLevel = new ArrayList<Integer>();
    		Queue<TreeNode> queue =  new LinkedList<TreeNode>();
    
    		if(root != null)
    		{
    			queue.add(root);
    			queue.add(null);
    		}
    
    		while(!queue.isEmpty())
    		{
    			TreeNode queueRoot = queue.poll();
    			if(queueRoot != null)
    			{
    				currentLevel.add(queueRoot.val);
    				if(queueRoot.left != null)
    				{
    					queue.add(queueRoot.left);
    				} 
    				if(queueRoot.right != null)
    				{
    					queue.add(queueRoot.right);
    				}
    			}
    			else
    			{
    				levelOrderTraversal.add(currentLevel);
    				if(!queue.isEmpty())
    				{
    					currentLevel = new ArrayList<Integer>();
    					queue.add(null);
    				}
    			}
    		}
    
    		return levelOrderTraversal;
    	}
    

  • 0
        public List<List<Integer>> levelOrder(TreeNode root) {
          List<List<Integer>> res = new ArrayList<List<Integer>>();
          if(root == null) return res; 
          Queue<TreeNode> q = new LinkedList<TreeNode>();
          q.offer(root);
          while(!q.isEmpty()){
            int size = q.size();
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
              TreeNode node = q.poll();
              list.add(node.val);
              if(node.left != null) q.offer(node.left);
              if(node.right != null) q.offer(node.right);
            }
            res.add(list);
          }  
          return  res;
        }

  • 0
    A

    @marcusgao My solution is same like yours


  • 0
    M

    @marcusgao Great minds think alike


Log in to reply
 

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