在 Java 中递归遍历二叉树而不使用 void 方法的最佳方法是什么？

Question

现在通过 MOOC 了解二叉树，我想递归遍历树并将数据添加到列表中，但我正在处理的作业不希望更改方法类型。我知道用 void 方法我可以做类似的事情：

 public static void preorder(TreeNode<T> root)
    {
        List<T> listOfData = new ArrayList<>();

        if (root == null) {
            return;
        }
 
       
        listOfData.add(root.getData());
 
        // Traverse the left subtree
        preorder(root.getLeft());
 
        // Traverse the right subtree
        preorder(root.right);
    }

但现在我的方法是

public List<T> preorder(TreeNode<T> root) {


        List<T> listOfData = new ArrayList<>();

        if (root != null) {
            listOfData.add(root.getData());
            preorder(root.getLeft());
            preorder(root.getRight());
        }

         return listOfData;
    }

在初始返回之后，列表似乎不会在每次堆栈调用时更新。

Answer 1

我知道用 void 方法我可以做类似的事情：[...]

您提供的

void

函数无法完成这项工作：调用者无法访问本地数组列表。此函数的每次调用都会创建一个最多包含一个成员的本地列表，当它返回时，该列表将不再可访问并标记为垃圾回收。

您要求让函数在没有 void

返回类型的情况下工作（如标题中所述），但确实在您的尝试中您只返回一个最多包含一个成员的列表。

问题在于您的代码忽略了递归调用返回的列表，但这是它们为您提供的唯一信息。如果您忽略这一点，您可能根本就不会拨打这些电话。他们不劳而获。

这是您尝试的更正：

public List<T> preorder(TreeNode<T> root) {
    List<T> listOfData = new ArrayList<>();
    if (root != null) {
        listOfData.add(root.getData());
        listOfData.addAll(preorder(root.getLeft() ));
        listOfData.addAll(preorder(root.getRight()));
    }
    return listOfData;
}