Share my Java solution use BFS


  • 0
    B

    Share my java solution used Breadth-First search. The tricky of BFS solution is how to know which level we are in. I use two integers "numOfLevel" and "numOfNextLevel" to record num of nodes in current level(which in processing) and next level.

    1.Initially numOfLevel=1 since first level just has 1 node, the root node. And numOfNextLevel = 0 since we do not know how many nodes in level 2.

    2.If root node has left child, numOfNextLevel++. If root node has right child, numOfNextLevel++. So we know how many nodes are in next level(It is 2 if root node has both left and right child).

    3.When we add node in current level to list, numOfLevel--. So in the first level, after add root node to list, numOfLevel is 0.

    4.When numOfLevel is 0, we know current level is done and it is time for next level. We already knew number of nodes in next level, so set numOfLevel = numOfNextLevel. Then the program enter next loop.

    Hope my explanation makes sense.

    public class Solution {
    
            public List<List<Integer>> levelOrder(TreeNode root) {
                List<List<Integer>> result = new LinkedList<List<Integer>>();
                
                //Store values of nodes for each level. This variable will be reused for each level.
                List<Integer> level = new LinkedList<Integer>();
        
                Queue<TreeNode> queue = new LinkedList<TreeNode>();
                queue.offer(root);
        
                //numOfLevel indicates the num of nodes in current level
                //numOfNextLevel indicated the num of nodes in next level
                int numOfLevel = 1, numOfNextLevel = 0;
        
                while(queue.peek() != null){
        
                    TreeNode node = queue.poll();
                    
                    //If current node has left or right, push them to queue. And numOfNextLevel++ since left and
                    //right child nodes belonging to next level.
                    if(node.left != null){
                        queue.offer(node.left);
                        numOfNextLevel++;
                    }
                    if(node.right != null){
                        queue.offer(node.right);
                        numOfNextLevel++;
                    }
        
                    //If numOfLevel is not equal to 0, it means there are still nodes in current level not be
                    //added to list "level".
                    if(numOfLevel != 0){
                        level.add(node.val);
                        numOfLevel--;
                    }
        
                    //If numOfLevel is equal to 0, it means we already added all the nodes in current level
                    //to list "level". Now it is time to process next level.
                    //1.Add current level to result.
                    //2.Point "level" to a new list object.
                    //3.We will process next level, so set numOfLevel = numOfNextLevel.
                    //4.Set numOfNextLevel = 0.
                    if(numOfLevel == 0){
                        result.add(level);
                        level = new LinkedList<Integer>();
                        numOfLevel = numOfNextLevel;
                        numOfNextLevel = 0;
                    }
                }
        
                return result;
            }
    
        }

Log in to reply
 

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