Iterative bfs Java Solution with explanation


  • 0
    V

    Since we need to get nodes of the tree from right side view, we give nodes on the right a higher priority
    than those on the left.

    q.add(node.right);

    q.add(node.left);

    By doing so , when we iterate over the nodes in the queue , only every first non -null element of
    a particular level of tree will be added to the list .

    If the question had been to return nodes which we could see from left side , then we only need to change the order in which we give priority and add them,i.e, it would be

    q.add(node.left);

    q.add(node.right);

    public List<Integer> rightSideView(TreeNode root) {
            
            TreeNode node = root;
            boolean flag = false;
            int length = 0;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            List<Integer> nodes_from_right_view = new ArrayList<Integer>();
            
            if(root == null)
            return nodes_from_right_view;
            
            
            q.add(node);
            
            
            while(!q.isEmpty())
            {
                length = q.size();
                flag = false;
                
                for(int i=0;i<length;++i)
                {
                    node = q.remove();
                    if(node == null)
                    continue;
                    
                    if(!flag)
                    {
                        nodes_from_right_view.add(node.val);
                        flag = true;
                    }
                    
                    q.add(node.right);
                    q.add(node.left);
                }
                
            }
            
            
            
            return nodes_from_right_view;
        }

Log in to reply
 

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