使用带有 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) {

    if (current != null) {

        getAllWordHelpers(list, current.getLeftChild());

        list.add(current.getWord());

        getAllWordHelpers(list, current.getRightChild());

    }

}

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) {

    if(words == null) words = new ArrayList(); 

    if (current != null) {

      getAllWordsHelper(words, current.getLeftChild());

      list.add(current.getWord());

      getAllWordsHelper(words, current.getRightChild());

    }

    return words;

  }

}