Java - Values are added multiple times in a list

Question

I'm trying to add some sub lists in a List<List<Integer>> once. But the problem is, it's getting added multiple times.

This is the code:

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null) return null;
        
        List<List<Integer>> res = new ArrayList<>();
        Queue<Pair> q = new LinkedList<>();
        
        q.add(new Pair(root, 0));
        
        while(!q.isEmpty()) {
          Pair tmp = q.poll();
          int data = tmp.root.val;
          int level = tmp.level;
          
          List<Integer> list;
          // get number of sublists in res
          if(res.size() == level) {
            list = new ArrayList<>();
            list.add(data);
          }
          
          else {
            list = res.get(level);
            System.out.println("existing list = " + list);
            if(level % 2 == 0) {
              list.add(data);
            }
            else list.add(0, data);
          }
          // By now, the sublists are populated
          
          System.out.println("list = " + list);
          // this shows the correct ans
          
          res.add(list);
          // this shows duplicated sublist

          System.out.println("res = " + res);
          
          if(tmp.root.left != null) q.add(new Pair(tmp.root.left, level + 1));
          if(tmp.root.right != null) q.add(new Pair(tmp.root.right, level + 1));
        }
      
      return res;
    }
  
    class Pair {
      TreeNode root;
      int level;
      
      Pair(TreeNode root, int level) {
        this.root = root;
        this.level = level;
      }
    }
}

Please help me on this.

Thanks in advance.

P.S: I think it's a silly mistake somwehere or a blunder.

This looks like a question that might be best answered by stepping through your code with your debugger to see what is being added where. What happens when you do this? — Hovercraft Full Of Eels
– Hovercraft Full Of Eels, Commented Jun 4, 2021 at 10:46
In that else, I'm trying to get existing list and add elements basis of level. — mrLovaLova
– mrLovaLova, Commented Jun 4, 2021 at 10:55

dpx98 · Accepted Answer · 2021-06-04 11:02:42Z

1

This is happening because you're adding the list again and again. You need to add the list in your resulting list i.e res only when there is no list present in res corresponding to that particular level.

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>(); // you don't need to return null, return empty list.
        
        List<List<Integer>> res = new ArrayList<>();
        Queue<Pair> q = new LinkedList<>();
        
        q.add(new Pair(root, 0));
        
        while(!q.isEmpty()) {

          int n = q.size();

          for(int i = 0 ; i  < n ; i++){

            Pair tmp = q.poll();
            int data = tmp.root.val;
            int level = tmp.level;
            
            List<Integer> list;
            // get number of sublists in res
            if(res.size() == level) {
              list = new ArrayList<>();
              list.add(data);
              res.add(list); // You need to add list into res only when there is no list corresponding to that level.
            }
            
            else {
              list = res.get(level);
              // System.out.println("existing list = " + list);
              if(level % 2 == 0) {
                list.add(data);
              }
              else list.add(0, data);
            }

            
            if(tmp.root.left != null) q.add(new Pair(tmp.root.left, level + 1));
            if(tmp.root.right != null) q.add(new Pair(tmp.root.right, level + 1));
          }
        }
        return res;
    }
}
    
class Pair {
  TreeNode root;
  int level;

  Pair(TreeNode root, int level) {
    this.root = root;
    this.level = level;
  }
}

edited Jun 4, 2021 at 11:02

answered Jun 4, 2021 at 10:50

dpx98

608 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mrLovaLova Over a year ago

if(res.get(level) == null) res.add(list). Are you suggesting this?

dpx98 Over a year ago

I've made the changes in above mentioned answer. Kindly check and let me know if you need any more clarification.

mrLovaLova Over a year ago

It works! Thanks a lot @Parundeep. It was a silly mistake on my end. Thanks for the help once again.

Collectives™ on Stack Overflow

Java - Values are added multiple times in a list

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related