二叉树遍历为何需要辅助函数？单函数实现问题咨询

先看你写的单函数版本存在的问题：

1. 编译错误：返回类型不匹配：当root == null时，你写的是return;，但函数声明要求返回List<Integer>，这里必须返回一个空列表，比如return new ArrayList<>();。
2. 函数签名不匹配：你调用preorderTraversal(root.left, answer);，但你的函数只有一个TreeNode参数，不存在带两个参数的重载方法，这会直接编译失败。

辅助函数的作用 #

用辅助函数主要解决这几个问题：

• 避免重复创建列表：如果不用辅助函数，每次递归都新建列表，最后还得把各个递归分支的列表合并起来，不仅代码繁琐，还会增加内存开销和合并时间。辅助函数版本是把同一个列表传递给所有递归调用，所有节点值都直接加到这个列表里，效率更高。
• 符合题目要求的函数签名：大多数OJ平台的题目会固定函数签名为public List<Integer> preorderTraversal(TreeNode root)，不能随便加参数。辅助函数可以在类内部定义，用来处理带列表参数的递归逻辑，对外保持题目要求的接口。
• 职责分离，逻辑更清晰：主函数只负责初始化结果列表和返回最终结果，辅助函数专注于前序遍历的递归逻辑，代码结构更直观。

不用辅助函数的正确实现 #

如果一定要用单函数实现，得改成每次递归返回子树的遍历结果，然后合并到当前列表里，代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        if (root == null) {
            return answer;
        }
        // 先添加根节点值
        answer.add(root.val);
        // 合并左子树的遍历结果
        answer.addAll(preorderTraversal(root.left));
        // 合并右子树的遍历结果
        answer.addAll(preorderTraversal(root.right));
        return answer;
    }
}

不过这个版本和辅助函数版本相比，每次递归都会创建新的列表，然后通过addAll合并，性能不如辅助函数版本高效，尤其是树的节点较多时，差异会更明显。

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