Java中不使用void方法递归遍历二叉树并收集节点数据的正确方式？

你当前的代码问题在于每次递归调用preorder都会新建一个独立的ArrayList，递归返回的子树遍历结果没有被合并到当前方法的列表中，所以最终只有根节点的数据被返回。下面是两种符合方法签名要求的正确实现：

方法1：合并递归返回的列表 #

直接利用递归调用返回的List，通过addAll合并到当前列表中，代码简洁直观：

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

方法2：使用辅助方法（性能更优） #

创建一个共享的List，通过私有辅助方法递归填充，避免多次创建和合并List的开销，这是实际开发中更常用的方式：

public List<T> preorder(TreeNode<T> root) {
    List<T> listOfData = new ArrayList<>();
    preorderHelper(root, listOfData);
    return listOfData;
}

// 私有辅助方法，负责递归遍历并填充共享的List
private void preorderHelper(TreeNode<T> root, List<T> list) {
    if (root == null) {
        return;
    }
    list.add(root.getData());
    preorderHelper(root.getLeft(), list);
    preorderHelper(root.getRight(), list);
}

另外需要注意：你提供的void版本的前序遍历代码也是错误的——每次调用preorder都会新建局部的listOfData，递归过程中无法收集所有节点的数据，正确的void遍历应该像上面的辅助方法一样，把List作为参数传入。

内容的提问来源于stack exchange，提问作者BengalTiger