带返回类型数组的递归树遍历方法

Question

有没有办法以递归方式遍历树并返回一个作用于该递归方法的数组？

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

这是我之前建议的代码:

private List nodeValues = new ArrayList();

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

正如你所看到的那样,ArrayList它超出了递归范围 - 因此返回它并没有多大意义.有一个更好的方法吗？

Answer 1

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;
}