Kotlin递归树调用出现NullPointerException，如何修复？

你的代码存在几个核心问题，直接导致了空指针异常和输出不符合预期：

1. 参数类型错误导致空值检查无效 #

DFSRecursive的参数是TreeNode<Char>（非可空类型），Kotlin会强制保证传入的root不可能为null，所以if(root == null)这个判断完全不会触发。而你用!!强制解包root.right和root.left，当节点没有子树时（比如d、e的左右子节点都是null），直接抛出NullPointerException。

2. 递归时每次新建列表，无法收集所有节点 #

每次递归调用都创建新的mutableListOf<Char>，导致每个递归栈里的列表都是独立的，最后只能打印当前节点的key，根本没法汇总整棵树的节点。

3. 递归顺序错误，不符合前序遍历要求 #

你期望的输出[a, b, d, e, c, f]是前序遍历（根->左->右），但当前代码是先递归右子树、再左子树、最后加当前节点，顺序完全颠倒。

修复后的代码 #

方案1：通过参数传递列表收集结果 #

class TreeNode<T>(var key: T){
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

// 递归函数：传入可空的根节点，以及用于收集结果的列表
fun DFSRecursive(root: TreeNode<Char>?, results: MutableList<Char>) {
    // 根节点为null时直接返回
    root ?: return
    // 前序遍历：先加当前节点，再递归左、右子树
    results.add(root.key)
    DFSRecursive(root.left, results)
    DFSRecursive(root.right, results)
}

fun buildTree(): TreeNode<Char>{
    val a = TreeNode('a')
    val b = TreeNode('b')
    val c = TreeNode('c')
    val d = TreeNode('d')
    val e = TreeNode('e')
    val f = TreeNode('f')

    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.right = f

    return a
}

// 调用示例
fun main() {
    val root = buildTree()
    val results = mutableListOf<Char>()
    DFSRecursive(root, results)
    println(results) // 输出：[a, b, d, e, c, f]
}

方案2：让递归函数返回列表（更函数式） #

class TreeNode<T>(var key: T){
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

fun DFSRecursive(root: TreeNode<Char>?): List<Char> {
    root ?: return emptyList()
    // 前序遍历：当前节点 + 左子树结果 + 右子树结果
    return listOf(root.key) + DFSRecursive(root.left) + DFSRecursive(root.right)
}

fun buildTree(): TreeNode<Char>{
    val a = TreeNode('a')
    val b = TreeNode('b')
    val c = TreeNode('c')
    val d = TreeNode('d')
    val e = TreeNode('e')
    val f = TreeNode('f')

    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.right = f

    return a
}

fun main() {
    val root = buildTree()
    println(DFSRecursive(root)) // 输出：[a, b, d, e, c, f]
}

关键修复点说明 #

• 将递归函数的参数改为TreeNode<Char>?，允许传入null，并用root ?: return安全处理空节点。
• 移除!!强制解包，改用安全的递归调用（当子节点为null时直接返回，不会触发空指针）。
• 调整递归顺序为根->左->右，匹配你期望的前序遍历输出。
• 要么通过参数传递列表收集所有节点，要么让函数返回子树的遍历结果并合并，避免每次递归新建独立列表。

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