Reverse iterative BFS solution


  • 0
    L
        // Reverse BFS iteration. Each level in the tree gets the right-most integer added
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if (root == null) return ret;
            queue.add(root);
            queue.add(null);
            ret.add(root.val);
            while(!queue.isEmpty()){
                TreeNode node = queue.poll();
                if (node == null){
                    queue.add(null);
                    if (queue.peek() == null){
                        break; // Finished the tree
                    } else {
                        ret.add(queue.peek().val); // Add the right hand side in
                        continue;
                    }
                }
                if (node.right != null) {
                    queue.add(node.right);
                } 
                if (node.left != null) {
                    queue.add(node.left);
                }
            }
            return ret;
        }
    

Log in to reply
 

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