2

有没有办法递归遍历树并返回一个范围为该递归方法的数组？

所以我最近回答了别人关于这个话题的问题。这个问题可以在这里找到：SO Question。我的解决方案使用了递归范围之外的数组，因此该方法不能（或至少可能不应该）返回该数组。但是，有没有办法编写一个遍历树的递归方法，使其返回一个数组？即使编写一个调用递归方法的初始方法也可以，但我想不出一个好的方法来做到这一点。

这是我之前建议的代码：

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}

如您所见，ArrayList它超出了递归的范围 - 因此返回它没有多大意义。有一个更好的方法吗？

4

3 回答 3

5 
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;
}
于 2013-06-08T05:21:30.607 回答
2

有一个替代方案，但它涉及两次遍历树。如果我的第一个答案中的数组操作让您感到悲伤，您只会使用这种替代方法。这种方法首先为每个节点提供一个索引（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);
}
于 2013-06-08T15:47:06.753 回答
0

在c中，您可以拥有静态函数变量，（即，在函数的一次迭代中将值添加到列表中意味着该值将在下一次迭代中出现在列表中 - 如果列表是静态的）但使用它们不是您建议的问题的最佳（最佳）解决方案。所以，我认为您正在搜索静态变量，但这不是使用它们的合适情况。

于 2013-06-08T05:25:47.283 回答