java 如何使用递归函数返回 ArrayList
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27886116/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to return an ArrayList with an recursive function
提问by chris1791
I am new at java and i fight my way through... I have to do some homework and i resolve a lot from it, but at some points i dont know how to do it. My Problem: I must build some functions for a binary Tree (such as add nodes, count nodes, delete nodes, etc). Most of them i could find myself the algorithm. Now i struggle with a recursive method. I put commentaries into it to explain what my problem is:
我是 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;
}
回答by Peter Lawrey
There is two way of doing this, simple but inefficient.
有两种方法可以做到这一点，简单但效率低下。
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;
}
This generates loads of lists and Object[] to hold them. A more efficient way is to provide a List to populate.
这会生成大量列表和 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;
}
This creates far less objects (possibly none if the list has a large enough capacity)
这会创建更少的对象（如果列表具有足够大的容量，则可能没有）
回答by Eran
You can pass the list to the recursive method. This way you only create the list once.
您可以将列表传递给递归方法。这样您只需创建一次列表。
public List<E> getPreOrderList() {
ArrayList<E> list = new ArrayList<E>();
getPreOrderListRec(list);
return list;
}
public void getPreOrderListRec(List<E> list) {
// logic of recursive method, which add elements to the list
}
