Java level order traversal implemented with queues


  • 0
    288 ms
    a second queue is used to record the level. 
    
    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> list = new LinkedList<>();
             if ( root == null)
               return list;
            Queue<TreeNode> nodeQueue = new LinkedList<>();
            Queue<Integer> levelQueue = new LinkedList<>();
            TreeNode node;
            int level;
            int max = 0; // the next expected level
            nodeQueue.offer(root);
            levelQueue.offer(0);
            while (!nodeQueue.isEmpty()){
                node = nodeQueue.poll();
                level = levelQueue.poll();
                if ( level == max){
                    list.add(node.val);
                    max++; // only the rightmost node of new level is added
                }
                if ( node.right != null) {
                     nodeQueue.offer(node.right);
                     levelQueue.offer(level + 1);
                }
                if ( node.left != null){
                    nodeQueue.offer(node.left);
                    levelQueue.offer( level + 1);
                }
            }
            return list;
        }
    }

Log in to reply
 

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