如何实现返回结果列表的Java二叉树递归前序遍历

二叉树节点定义 #

首先需要定义标准的二叉树节点类，这是遍历的基础：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

实现方式一：辅助递归（推荐，效率更高） #

通过辅助方法传递结果列表，避免频繁创建新集合，所有递归操作共享同一个列表：

import java.util.ArrayList;
import java.util.List;

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    // 辅助递归方法：处理当前节点并递归遍历左右子树
    private void traverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return; // 空节点直接返回，终止递归
        }
        // 前序遍历顺序：根节点 -> 左子树 -> 右子树
        result.add(node.val);
        traverse(node.left, result);
        traverse(node.right, result);
    }
}

核心逻辑说明

• 主方法初始化空列表，传入辅助方法
• 辅助方法先判断节点是否为空（避免空指针异常）
• 按照前序规则，先将当前节点值加入列表，再递归遍历左、右子树
• 因为列表是引用类型，递归过程中所有修改都会同步到主方法的列表中

实现方式二：递归直接返回列表（代码更简洁） #

每次递归创建新列表，合并当前节点值与左右子树的遍历结果：

import java.util.ArrayList;
import java.util.List;

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 前序顺序：根节点值 -> 左子树结果 -> 右子树结果
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }
}

优缺点说明

• 优点：代码直观，无需额外辅助方法
• 缺点：每次递归都会创建新列表，对于深度大的树会产生较多临时对象，效率略低

常见错误排查 #

如果你自己写的递归方法无法正常运行，大概率是以下问题：

1. 未处理空节点：直接访问node.val导致NullPointerException，必须先判断node == null
2. 递归顺序错误：把result.add(node.val)放在左右递归之后，变成了后序遍历；放在左递归之后右递归之前，变成了中序遍历
3. 未合并子树结果：调用递归方法但未将返回的列表合并到当前结果中，最终只返回根节点值（如下错误示例）：

// 错误示例：丢弃了左右子树的遍历结果
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.add(root.val);
    preorderTraversal(root.left); // 这里的返回值被丢弃
    preorderTraversal(root.right);
    return result; // 最终仅包含根节点值
}

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