Java 2ms BFS solution


  • 7
    B
    public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<TreeNode> toUse = new ArrayList<>();
        List<List<Integer>> retValue = new ArrayList<>();
        if( root != null)
        {
        	toUse.add(root);
        }
        
        while (toUse.size() != 0)
        {
            List<Integer> result  = new ArrayList<>();
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode node : toUse)
            {
                result.add(node.val);
                
                if (node.left != null)
                {
                    next.add(node.left);
                }
                
                if (node.right != null)
                {
                    next.add(node.right);
                }
            }
            retValue.add(result);
            toUse = next;            
        }
        Collections.reverse(retValue);
        return retValue;
    }
    

    }


  • 0
    J

    This is a very good solution, thanks a lot!


  • 0
    Z

    So what if there is a follow up like, Can you do it without using reverse?


  • 0
    B

    As in reverse the list by hand(without the aid of the Collections library)?


  • 0
    G

    Similar solution using a queue.

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            
            if(root != null)  
                queue.add(root);
            
            while(!queue.isEmpty()){
                int size = queue.size();
                List<Integer> level = new ArrayList<>();
                for(int i=0; i<size; 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);
                }
                result.add(level);
            }
            Collections.reverse(result);
            return result;
        }
    

Log in to reply
 

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