如何用Clojure实现二叉树从根到叶的所有路径递归函数？

首先指出你当前代码里的几个核心问题：

• 错误使用def修改参数：Clojure是纯函数式语言，def会创建全局变量，递归过程中不同分支会污染同一个P，导致路径混乱。应该通过参数传递新的集合（因为conj返回新集合，不修改原集合）。
• 分支递归逻辑错误：当前代码里右子节点存在的情况，仍然调用(helper (T :left) ...)，else分支也两次调用左子树，完全没处理右子树，这会导致右路径完全丢失。
• 副作用优先而非返回结果：用print直接输出路径是副作用操作，函数式编程应该让函数返回结果集合，方便后续处理。
• 无用的i参数：你的代码里i没有实际作用，完全可以移除。

正确的递归实现思路 #

Clojure里处理这类问题，核心是通过递归传递当前路径，在叶子节点收集完整路径，分三种情况处理：

1. 节点为空：返回空列表（无路径）
2. 节点是叶子（左右子节点都为空）：将当前节点值加入路径，作为一条完整路径返回
3. 非叶子节点：递归遍历左右子树，将当前节点值加入当前路径后传递给子递归，最后合并左右子树的结果

重构后的代码示例 #

方式一：嵌套辅助函数（推荐） #

(defn root-to-leaf-paths [root]
  ;; 定义内部辅助函数，接收当前节点和当前路径
  (letfn [(helper [node current-path]
            (cond
              ;; 空节点，无路径返回
              (nil? node) []
              ;; 叶子节点，返回包含当前完整路径的列表
              (and (nil? (:left node)) (nil? (:right node)))
              [(conj current-path (:value node))]
              ;; 非叶子节点，递归左右子树，合并结果
              :else
              (concat
               (helper (:left node) (conj current-path (:value node)))
               (helper (:right node) (conj current-path (:value node))))))]
    ;; 从根节点开始，初始路径为空
    (helper root [])))

方式二：无辅助函数的递归 #

(defn root-to-leaf-paths [node]
  (cond
    (nil? node) []
    (and (nil? (:left node)) (nil? (:right node))) [[(:value node)]]
    :else
    (concat
     ;; 把当前节点值加到左子树每条路径的开头
     (map #(conj % (:value node)) (root-to-leaf-paths (:left node)))
     ;; 把当前节点值加到右子树每条路径的开头
     (map #(conj % (:value node)) (root-to-leaf-paths (:right node))))))

测试示例 #

假设你的示例二叉树结构如下：

(def sample-tree
  {:value 1
   :left {:value 2
          :left {:value 4}
          :right {:value 5}}
   :right {:value 3}})

调用函数后会得到所有根到叶的路径：

(root-to-leaf-paths sample-tree)
;; => [[1 2 4] [1 2 5] [1 3]]

额外说明 #

• 不要在递归中使用def或set!修改变量，Clojure的核心是不可变数据，所有状态变化都通过参数传递新的不可变值实现。
• 优先让函数返回纯数据而非产生副作用（比如print），这样函数更易测试、复用和组合。

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