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.

Answer 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;
  }
}