своп узлов в бинарном дереве в Clojure

Question

Я пытаюсь решить [эту] [1] проблема, когда вам нужно создать бинарное дерево, которое выглядит следующим образом:

   1 
      /\ 
      2 3 
     //
      4 5 
     //
     / /\ 
    //\ 
     6 7 8 
     \ /\ 
     \ / \ 
      9 10 11 

От этого входа где -1 представляет собой null node

[2 3] [4 -1] [5 -1] [6 -1] [7 8] [-1 9] [-1 -1] [10 11] [-1 -1] [-1 -1] [-1 -1] 

Как только вы это сделаете, проблема попросит вас обменивать узлы на заданной глубине.

До сих пор у меня есть этот код, который создает дерево:

(ns scratch.core 
    (require [clojure.string :as str :only (split-lines join split)])) 

(defn numberify [str] 
    (vec (map read-string (str/split str #" ")))) 

(defrecord TreeNode [val left right]) 

(defn preprocess-input [n xs] 
    (let [source (map vector (range 1 n) xs)] 
    (->> source 
     (map (fn [[k v]] 
       {k v})) 
     (into {})))) 

(defn build-tree [val source] 
    (when-let [[l r] (get source val)] 
    (TreeNode. val (build-tree l source) (build-tree r source)))) 

(let [input "11\n2 3\n4 -1\n5 -1\n6 -1\n7 8\n-1 9\n-1 -1\n10 11\n-1 -1\n-1 -1\n-1 -1\n2\n2\n4" 
     lines (str/split-lines input) 
     tree-length (read-string (first lines)) 
     tree-lines (map numberify (drop 1 (take (inc tree-length) lines))) 
     tree-source (preprocess-input tree-length tree-lines) 
     tree (build-tree 1 tree-source) 
     swap-depths (map read-string (vec (take-last (Integer/parseInt (get lines (inc tree-length))) lines)))]) 

Я полностью застрял с тем, как поменять узлы, я попробовал эту функцию:

(defn walk-tree [node curr swap-depth] 
    (when node 
    (let [left (:left node) 
      right (:right node) 
      val (:val node)] 
     (if (= curr swap-depth) 
     (TreeNode. val (walk-tree right (inc curr) swap-depth) (walk-tree left (inc curr) swap-depth)) 
    (TreeNode. val (walk-tree left (inc curr) swap-depth) (walk-tree right (inc curr) swap-depth)))))) 

Но я думаю, что я должен идти в BFS, а не в DFS, потому что, хотя я могу поменять узел таким образом, он будет заменен обратно при правильном узле.

Answer 1

Как я уже сказал в комментарии, я бы подойти к этому в этих двух направлениях:

1. Возьмите это как проблему манипуляций со строками. Сначала разделите его на ряд строк. Затем определите функцию, которая принимает m и a-seq, и ест первые m элементов из a-seq и производит n, где n указывает количество действительных узлов этого слоя и оставшегося seq. Повторите это depth раз, и теперь вы находитесь на заданной глубине. Делайте все, что требуется. Должны быть и другие жизнеспособные методы.
2. Построить древовидную структуру. Но вместо простого сохранения значения, заданного в каждом узле, глубина также прилагается. Затем используйте clojure.walk/postwalk для перемещения по дереву, обновляйте значение при просмотре узлов на заданной глубине.