java 返回类型数组的递归树遍历方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16996314/
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
Recursive Tree Traversal Method With Return Type Array
提问by sage88
Is there a way to recursively traverse a tree and return an array that is scoped to that recursive method?
有没有办法递归遍历树并返回一个范围为该递归方法的数组？
So I recently answered someone else's question on this topic. That question can be found here: SO Question. My solution uses an array outside of the scope of the recursion, and therefore the method cannot (or at least probably should not) return the array. However, is there a way to write a recursive method for traversing trees such that it returns an array? Even writing an initial method that calls the recursive one would be fine, but I can't think of a good way to do this.
所以我最近回答了别人关于这个话题的问题。这个问题可以在这里找到：SO Question。我的解决方案使用了递归范围之外的数组，因此该方法不能（或至少可能不应该）返回该数组。但是，有没有办法编写一个递归方法来遍历树，使其返回一个数组？即使编写一个调用递归方法的初始方法也可以，但我想不出一个好的方法来做到这一点。
Here's the code that I suggested before:
这是我之前建议的代码：
private List nodeValues = new ArrayList();
public void traversePreRecursive(BinarySearchTreeNode node)
{
if (node != null)
{
nodeValues.add(node.getValue());
traversePreRecursive(node.getLeft());
traversePreRecursive(node.getRight());
}
}
As you can see the ArrayListis outside of the scope of the recursion - And therefore returning it doesn't make a lot of sense. Is there a better way to do this?
正如您所看到的ArrayList，超出了递归的范围——因此返回它没有多大意义。有一个更好的方法吗？
回答by Software Engineer
public static List traversePreRecursive(Node node) {
if (node == null) return new ArrayList();
List nodeValues = new ArrayList();
nodeValues.add(node.getValue());
nodeValues.addAll(traversePreRecursive(node.getLeft()));
nodeValues.addAll(traversePreRecursive(node.getRight()));
return nodeValues;
}
回答by Software Engineer
There is an alternative, but it involves two passes over the tree. You would only employ this alternative if the array operations in my first answer were giving you grief. This approach starts by providing an index for each of the nodes (the index()method) -- basically working out which element of the array a node should occupy before we actually create the array. This also gives me a count of nodes (size). I then allocate an array (list) big enough to hold all the nodes and pass it into a method (addToList) that copies the node-references into the previously identified element in the array.
有一个替代方案，但它涉及两次遍历树。如果我的第一个答案中的数组操作让您感到悲伤，您只会使用这种替代方法。这种方法首先为每个节点（index()方法）提供一个索引——基本上是在我们实际创建数组之前确定节点应该占用数组的哪个元素。这也给了我节点数 ( size)。然后我分配一个list足够大的数组 ( ) 以容纳所有节点，并将其传递给一个方法 ( addToList)，该方法将节点引用复制到数组中先前标识的元素中。
public static List<Node> getNodes(Node a) {
int size = index(a, 0);
List<Node> list = new ArrayList<Node>(size);
addToList(a, list);
return list;
}
private static int index(Node node, int index) {
if (node == null) return index;
node.setIndex(index);
int iLeft = index(node.getLeft(), index++);
int iRight = index(node.getRight(), iLeft++);
return iRight + 1;
}
private static void addToList(Node node, List<Node> list) {
if(node == null) return;
list.add(node.getIndex(), node);
addToList(node.getLeft(), list);
addToList(node.getRight(), list);
}
回答by jmpyle771
In c you can have static function variables,(Ie, adding a value to a list in one iteration of a function means that that value will be in the list in the next iteration--if the list is static) but using them isn't the best (most optimal) solution for the problem you are suggesting. So, I think you are searching for static variables, but this isn't an appropriate case to use them.
在 c 中，您可以拥有静态函数变量，（即，在函数的一次迭代中向列表添加值意味着该值将在下一次迭代中出现在列表中——如果列表是静态的）但使用它们不是t 针对您建议的问题的最佳（最优）解决方案。所以，我认为您正在搜索静态变量，但这不是使用它们的合适情况。
