如何使用递归函数返回ArrayList

我是java新手，我一直在努力…我必须做一些功课，我从中解决了很多，但在某些方面，我不知道该怎么做。 我的问题：我必须为二叉树构建一些函数（例如添加节点，计数节点，删除节点等）。 他们中的大多数我都能找到自己的算法。 现在我正在努力使用递归方法。 我在其中添加了注释来解释我的问题是什么：

public List 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 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 list = new ArrayList(); 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; } 

Answer 1

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

 public List getAll() { List 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 []来保存它们。 一种更有效的方法是提供一个List来填充。

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

这会创建更少的对象（如果列表具有足够大的容量，则可能没有）

Answer 2

您可以将列表传递给递归方法。 这样您只需创建一次列表。

 public List getPreOrderList() { ArrayList list = new ArrayList(); getPreOrderListRec(list); return list; } public void getPreOrderListRec(List list) { // logic of recursive method, which add elements to the list }