泛型PostOrder ( BinarySearchTree )中的BinarySearchTree输出

Question

我在做一些编码作业时遇到了一点小麻烦。我应该编写一个通用的二进制搜索树实用程序，包括一个返回树的ArrayList遍历版本的postOrder的方法。我的代码编译，但是它为除空树之外的所有树抛出一个NullPointerException。我的错误在哪里？

public ArrayList<T> postOrder(BinarySearchTree<T> tree) {
    if (tree == null) {
        return null;
    } else {
        ArrayList<T> post = new ArrayList<T>();
        post.addAll(postOrder(tree.left));
        post.addAll(postOrder(tree.right));
        post.add(tree.thing);
        return post;
    }
}

BinarySearchTree类是：

public class BinarySearchTree<T> {
/**
 * The key by which the thing is refered to. Must be unique.
 */
public int key;

/**
 * The thing itself.
 */
public T thing;

/**
 * The left sub-tree
 */
public BinarySearchTree<T> left;

/**
 * The right sub-tree
 */
public BinarySearchTree<T> right;
Biny
/**
 * Create a new binary search tree without children.
 * @param key the key by which the thing is refered to
 * @param thing the new thing
 */
public BinarySearchTree(int key, T thing)
{
    this.key = key;
    this.thing = thing;
    this.left = null;
    this.right = null;
}

/**
 * Create a new binary search tree
 * @param key the key by which the thing is refered to
 * @param thing the thing which is managed by the new binary search tree
 * @param left the left sub-tree of the new binary search tree
 * @param right the right sub-tree of the new binary search tree
 */
public BinarySearchTree(int key, T thing, BinarySearchTree<T> left, BinarySearchTree<T> right)
{
    this.key = key;
    this.thing = thing;
    this.left = left;
    this.right = right;
}

谢谢你的帮助

编辑:我正在用Strings测试我的代码，但希望这并不重要，因为我使用的是泛型类型。

Answer 1

试试这个：

public ArrayList<T> postOrder(BinarySearchTree<T> tree) {
    if (tree == null) {
        return null;
    } else {
        ArrayList<T> post = new ArrayList<T>();
        ArrayList<T> l = postOrder(tree.left);
        if (l != null) post.addAll(l);
        ArrayList<T> r = postOrder(tree.right);
        if (r != null) post.addAll(r);
        post.add(tree.thing);
        return post;
    }
}