clojure 中二叉树从根到叶的路径

Question

我正在尝试实现一个递归函数，该函数可以在 clojure 中的二叉树中找到从根到叶子的所有路径，但我被卡住了。这是树的外观示例：

我一直试图从 java 中的实现中寻找灵感 https://www.geeksforgeeks.org/given-a-binary-tree-print-all-root-to-leaf-paths/ ，但我仍然不知道如何在 clojure 中编写类似的函数。这是我到目前为止编写的辅助函数。

 (defn helper

[T P i]

(if (not (= nil T))
    (do (def P (conj P (T :value)))
        P
    )
)

(if (isbranch? T)
    (cond
       (and (not (= nil (T :left))) (= nil (T :right))) (helper (T :left) P (+ i 1))
       (and (not (= nil (T :right))) (= nil (T :left))) (helper (T :left) P (+ i 1))
       :else (do (helper (T :left) P (+ i 1)) (helper (T :left) P (+ i 1)))
    )
    (print P)
))

有人可以解释我应该从哪里开始吗？

Answer 1

我假设通过阅读问题中的代码来表示树是这样的：

(def input {:value 10
            :left {:value 8 :left {:value 3} :right {:value 5}}
            :right {:value 2 :left {:value 2}}})

除此之外，我不清楚问题中提供的代码应该如何工作。

这是我建议的递归解决方案：

(defn- all-paths-recursive-sub [dst path {:keys [value left right]}]
  (let [children (remove nil? [left right])
        path (conj path value)]
    (if (empty? children)
      (conj dst path)
      (reduce (fn [dst subtree] (all-paths-recursive-sub dst path subtree))
              dst
              children))))

(defn all-paths-recursive [tree]
  (all-paths-recursive-sub [] [] tree))

(all-paths-recursive input)
;; => [[10 8 3] [10 8 5] [10 2 2]]

这是一个迭代解决方案：

(defn all-paths-iterative [tree]
  (loop [stack [[[] tree]]
         result []]
    (if (empty? stack)
      result
      (let [[[path {:keys [value left right]}] & stack] stack
            children (remove nil? [left right])
            path (conj path value)]
        (if (empty? children)
          (recur stack (conj result path))
          (recur (into stack (map (partial vector path)) children) result))))))

(all-paths-iterative input)
;; => [[10 2 2] [10 8 5] [10 8 3]]

Answer 2

我认为 Rulle 的递归解决方案比必要的更复杂。

for

是将序列转换为其他序列的首要工具，尤其是当它们像树一样嵌套时。

(defn paths-to-leaves [{:keys [left right value]}]
  (if (every? nil? [left right])
    [[value]]
    (for [child (filter some? [left right])
          path (paths-to-leaves child)]
      (cons value path))))

最重要的是，这个解决方案是惰性的，所以你可以在大树上使用它而无需一次具体化所有路径。当然，它仍然必须先到达一片叶子，然后才能生成通往那片叶子的路径，但它不必查看所有这些叶子。

Answer 3

Spectre 是嵌套数据的绝佳工具。基于 递归使用 spectre 的解决方案：

(require '[com.rpl.specter :refer :all])

(def input {:value 10
            :left  {:value 8 :left {:value 3} :right {:value 5}}
            :right {:value 2 :left {:value 2}}})

(def leaf-paths
  (recursive-path [] RECUR
      (if-path #(some % [:left :right])
        [(collect-one :value) (submap [:left :right]) MAP-VALS RECUR]
        :value)))

(select leaf-paths input)
;; => [[10 8 3] [10 8 5] [10 2 2]]

虽然我会承认 spectre 有它自己的学习曲线，但上面可以稍微修改成一个对选择和修改都有用的导航器：

(def leaf-values
  (recursive-path [] RECUR
      (if-path #(some % [:left :right])
        [(submap [:left :right]) MAP-VALS RECUR]
        :value)))

(select leaf-values input)
;; [3 5 2]

(transform leaf-values #(* 100 %) input)
;; {:value 10,
;;  :left {:value 8, :left {:value 300}, :right {:value 500}},
;;  :right {:value 2, :left {:value 200}}}