Sortie de PostOrder dans un BinarySearchTree générique (Java)

Question

J'ai un peu de mal avec certains devoirs de codage. Je suis supposé écrire un utilitaire d'arbre de recherche binaire générique, incluant une méthode pour renvoyer une ArrayList de la traversion postOrder de l'arbre. Mon code compile, mais il lance une exception NullPointerException pour tous les arbres sauf des arbres vides. Où est mon erreur?

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

La BinarySearchTree classe est:

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

Merci de nous aider

Edit: Je teste mon code avec des chaînes, mais cela ne devrait pas d'importance, espérons que des types génériques utilisés .

Answer 1

Essayez ceci:

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