使用带有 ArrayList 的 BST 的中序遍历

Question

我正在完成一种作业方法，该方法使用字典中包含单词的 BST 的中序遍历。

我了解如何使用递归来完成中序遍历，但我无法将我的节点值包含在 ArrayList 中，这是该方法所必需的，因为每次该方法再次调用自身时，都会重新创建列表并重新创建所有其他以前的值丢失了。

 /**

   * Recursive Helper method that returns a list of all the words stored in the subtree rooted at

   * current sorted alphabetically from A to Z

   * 

   * @param current pointer to the current DictionaryWord within this dictionaryBST

   * @return an ArrayList of all the words stored in the subtree rooted at current

   */

  private static ArrayList<String> getAllWordsHelper(DictionaryWord current) {

    ArrayList<String> list = new ArrayList<String>();

    if (current != null) {

      getAllWordsHelper(current.getLeftChild());

      list.add(current.getWord());

      getAllWordsHelper(current.getRightChild());

    }

    return list;

  }

}

返回一个包含值的 ArrayList 是必需的，我无法将其更改为将一个值作为参数传入，因此我在解决此问题时遇到了一些麻烦 - 我在网上看到的所有其他示例仅打印当前节点。任何建议表示赞赏，谢谢！

Answer 1

问题是您没有对递归调用返回的值做任何事情。您需要将它们实际添加到列表中：list.addAll(getAllWordsHelpers(current.getLeftChild()));list.add(current.getWord();list.addAll(getAllWordsHelpers(current.getRightChild()));一种更有效的方法是将列表传递给方法，这样您就不需要继续创建新列表：private void getAllWordHelpers(List<String> list, DictionaryWord current) {&nbsp; &nbsp; if (current != null) {&nbsp; &nbsp; &nbsp; &nbsp; getAllWordHelpers(list, current.getLeftChild());&nbsp; &nbsp; &nbsp; &nbsp; list.add(current.getWord());&nbsp; &nbsp; &nbsp; &nbsp; getAllWordHelpers(list, current.getRightChild());&nbsp; &nbsp; }}

Answer 2

The problem is you want to store words across multiple call stacks during inorder traversal, which is possible only by using a global object which should be available to all call stacks during recursive calls.So here we have used a formal argument called words which represent a list object and this object will be common to all call stacks during recursive calls.ArrayList<String> words = getAllWordsHelper(current, null)private static ArrayList<String> getAllWordsHelper(DictionaryWord current, List<String> words) {&nbsp; &nbsp; if(words == null) words = new ArrayList();&nbsp;&nbsp; &nbsp; if (current != null) {&nbsp; &nbsp; &nbsp; getAllWordsHelper(words, current.getLeftChild());&nbsp; &nbsp; &nbsp; list.add(current.getWord());&nbsp; &nbsp; &nbsp; getAllWordsHelper(words, current.getRightChild());&nbsp; &nbsp; }&nbsp; &nbsp; return words;&nbsp; }}