java - 如何使用递归函数返回ArrayList

我是Java的新手，我在努力奋斗...
我必须做一些家庭作业，我从中解决了很多问题，但有时我不知道该怎么做。
我的问题:
我必须为二叉树构建一些功能(例如添加节点，计数节点，删除节点等)。他们中的大多数我都能找到自己的算法。现在我在用递归方法挣扎。
我在其中添加了评论以解释我的问题是:

    public List<E> getPreOrderList() {
    //TO DO:
    //this function should return  a list of the nodes in pre-order (value, left, right).
    //It must be implemented recursively!!!

    //THE PROBLEM:
    //If i create an ArrayList<E> inside the function, the
    //recursion will generate each time a new ArrayList.
    //At the end i get as result an ArrayList with only one node.
    ArrayList<E> list = new ArrayList<E>();

    if (this.value == null) {
        return null;
    }
    //If I just print out the nodes, the pre-order algorithm is OK,
    //but i need to return all nodes into an ArrayList.
    System.out.print(value + ", ");
    list.add(value);
    if (left != null) {
        left.getPreOrderList();
    }
    if (right != null) {
        right.getPreOrderList();
    }
    return list;
}

最佳答案

有两种方法可以做到，简单但效率低下。

public List<E> getAll() {
     List<E> list = new ArrayList<>();
     if (value != null) list.add(value);
     if (left != null) list.addAll(left.getAll());
     if (right != null) list.addAll(right.getAll());
     return list;
}

这将生成列表和Object []的负载以容纳它们。一种更有效的方法是提供要填充的列表。

public List<E> getAll(List<E> list) {
     if (value != null) list.add(value);
     if (left != null) left.getAll(list);
     if (right != null) right.getAll(list);
     return list;
}

这样创建的对象要少得多(如果列表具有足够的容量，则可能没有对象)