在 Java 中的二叉树中执行层序遍历时输出为空

Question

我想在 Java 的二叉树中执行层序遍历。基本上我需要将每个级别的节点值存储在一个数组列表中，并将这些不同的数组列表存储在一个数组列表中。在我的最终输出中，只显示空数组列表。我无法理解逻辑错误。谁能指导一下。

public class Solution {
        static ArrayList<ArrayList<Integer>> ourList=new ArrayList<>();
        static ArrayList<Integer>ourArray=new ArrayList<>();
        public static void breadth(Node root){
            Queue<Node> ourQueue=new LinkedList<>();
            ourQueue.add(root);
            while(!ourQueue.isEmpty()){
                int size=ourQueue.size();
                for(int i=0;i<size;i++){
                    Node poppedElement=ourQueue.poll();
                    ourArray.add(poppedElement.data);
                    if(poppedElement.left!=null){
                        ourQueue.add(poppedElement.left);
                    }
                    if(poppedElement.right!=null){
                        ourQueue.add(poppedElement.right);
                    }
                }
                ourList.add(ourArray);
                ourArray.clear();
            }
        }
    }

Answer 1

由于您希望在 ourList 中收集结果，因此您需要为保存在 ourArray 中的列表创建专用实例。所以，不是清除 ourArray，你应该 re-create 它：而不是

ourArray.clear();

写

ourArray= new ArrayList<>();

Answer 2

进行以下简短测试：

    ArrayList<ArrayList<Integer>> ourList=new ArrayList<>();
    ArrayList<Integer>ourArray=new ArrayList<>();
    //add values
    ourArray.add(1);  ourArray.add(2);  ourArray.add(3);  ourArray.add(4);
    ourList.add(ourArray);

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray.clear();
    System.out.println(ourList.get(0)); //prints []

原因是 ourList 包含对列表的引用。 ourArray 是对同一列表的引用，清除后，ourList 包含对空列表的引用。

现在测试提出的方案：

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray = new ArrayList<>();
    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]

另一种解决方案是“防御性副本”：

    ourList.add(new ArrayList<>(ourArray)); //add a copy of ourArray

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray.clear();
    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]

在 Java 中的二叉树中执行层序遍历时输出为空

Empty output while performing level order traversal in Binary trees in Java

java

arraylist

tree

breadth-first-search