元宝 深度思考 LeetCode 113.路径总和 || Kotlin实现

下面是 LeetCode 113（Path Sum II） 的 Kotlin 实现，代码风格符合 LeetCode 的提交规范，并附带了详细注释。

Kotlin 完整实现（可直接提交）

/**

• LeetCode 给定的 TreeNode 定义

• class TreeNode(varval: Int) {

• var left: TreeNode? = null

• var right: TreeNode? = null

• }
  */
  class Solution {

  // 存放所有满足条件的路径结果
  private val result = mutableListOf<List>()
  // 记录当前递归路径
  private val path = mutableListOf()

  fun pathSum(root: TreeNode?, targetSum: Int): List<List> {
  // 每次调用前清空（防止多个测试用例互相干扰，虽然 LeetCode 每次 new Solution 不需要，但养成好习惯）
  result.clear()
  path.clear()

  root?.let { dfs(it, targetSum, 0) } return result

  }

  /**

  • 深度优先搜索（DFS）

  • @param node 当前遍历的节点

  • @param targetSum 目标总和

  • @param currentSum 当前路径上的节点值总和
    */
    private fun dfs(node: TreeNode, targetSum: Int, currentSum: Int) {
    // 1. 将当前节点加入路径，并更新当前总和
    path.add(node.val)
    val newSum = currentSum + node.val

    // 2. 判断是否为叶子节点
    if (node.left == null && node.right == null) {
    // 如果是叶子节点且总和满足条件，将当前路径的拷贝加入结果集
    if (newSum == targetSum) {
    result.add(ArrayList(path)) // 关键：这里必须新建一个 List 拷贝
    }
    } else {
    // 3. 递归遍历左右子树
    node.left?.let { dfs(it, targetSum, newSum) }
    node.right?.let { dfs(it, targetSum, newSum) }
    }

    // 4. 回溯：离开当前节点，将其从路径中移除，以便探索其他分支
    path.removeAt(path.size - 1)
    }
    }

核心思路解析

步骤 说明
DFS 遍历 从根节点一直往下走，直到叶子节点。
路径记录 每访问一个节点，就把它的值加入
“path” 列表。
叶子节点判断 左右子节点都为
“null” 时，检查
“currentSum == targetSum”。
回溯（Backtrack） 递归返回前，执行
“path.removeAt(path.size - 1)”，撤销选择。

Kotlin 实现中的关键点

“ArrayList(path)” 拷贝路径因为
“path” 是
“MutableList”，在回溯过程中会不断被修改。如果直接
“result.add(path)”，后续修改会影响已存入结果集的数据，所以必须创建拷贝。
2. 处理 Kotlin 关键字
"val"LeetCode 中 TreeNode 的字段名是
“val”，而
“val” 是 Kotlin 的保留关键字，因此访问时必须使用反引号：
" node.val"。
3. 空安全（
“?.let”）利用 Kotlin 的
“?.let” 可以优雅地处理左右子节点为
“null” 的情况，避免显式的
“if (node.left != null)” 判断，代码更简洁。
4. 时间 & 空间复杂度

• 时间复杂度：O(N)，每个节点恰好被访问一次。
• 空间复杂度：O(N)，递归调用栈的深度以及存储路径所需的额外空间。

如果你希望看到迭代法（使用栈模拟 DFS）的 Kotlin 版本，或者想对比 Kotlin 与 Rust 在回溯处理上的差异，随时告诉我！