java - 尝试填充 BST 中的数组时如何通过递归方法保持计数

Question

我试图通过预序树遍历来填充数组，但我认为我在如何保持计数器正确方面犯了一个错误。我的 toString() 方法调用 preorder 方法，但它只输出 null。我该如何解决这个问题？

public AVLTreeNode[] preorder()
{
    /*
     * return an array of AVLTreeNodes in preorder
     */
    AVLTreeNode[] preorder = new AVLTreeNode[size];
    int count = 0;
    return preorder(root, count, preorder);
}

private AVLTreeNode[] preorder(AVLTreeNode data, int count, AVLTreeNode preorder[])
{
    if (data == null)
    {
        return preorder;
    }
    preorder[count] = data;
    if (data.getLeft() != null)
    {
        preorder(data.getLeft(), count++, preorder);
    }
    if (data.getRight() != null)
    {
        preorder(data.getRight(), count++, preorder);
    }
    return preorder;
}

Answer 1

count 的值错误，因为在使用 count++ 调用 preorder 时，count 的实际值会传递给该方法，并且之后 count 会增加。此外，从左节点返回后，count 的值可能比传递给右节点调用的值更高。解决办法有两种:

1. 使用全局private int count;，并在调用preorder之前将其设置为0。

2. 返回新的 count 而不是 AVLTreeNode[] 并将其分配给方法的本地 count 以获取正确的值。 AVLTreeNode[] preorder 也可以是私有(private)变量。