Java

Question

我正在尝试在 List<List<Integer>> 中添加一些子列表一次。但问题是，它被添加了多次。

这是代码：

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

请帮我解决这个问题。

提前致谢。

P.S: 我认为这是一个愚蠢的错误或失误。

Answer 1

发生这种情况是因为您一次又一次地添加列表。您需要在结果列表中添加列表，即仅当 res 中不存在与该特定级别对应的列表时才需要 res。

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

Java - 在列表中多次添加值

Java - Values are added multiple times in a list

binary-tree

breadth-first-search