Как я могу объединить два бинарных дерева в рубине?

Question

У меня есть 2 двоичных дерева [1,3,2,5] и [2,1,3, ноль, 4, ноль, 7], и мне нужно объединить их в одно дерево, используя язык программирования ruby.Таким образом, результат должен быть [3,4,5,5,4, null, 7]

Я попытался пройти оба указанных дерева в порядке предварительного порядка.

Что я делаю не так?

Я пытался использовать рекурсию:

def merge_trees(t1, t2)
  return if t1 == nil
  return if t2 == nil
  t1.val += t2.val
  t1.left = merge_trees(t1.left, t2.left);
  t1.right = merge_trees(t1.right, t2.right);
end

Answer 1

Как это?

[[1,3,2,5], [2,1,3,nil,4,nil,7]].
  sort_by(&:size).
  rotate.
  reduce(&:zip).
  map { |elems| elems.compact.reduce(&:+) }
#⇒ [3, 4, 5, 5, 4, nil, 7]

Answer 2

tree1 = [1, 3, 2, 5]
tree2 = [2, 1, 3, nil, 4, nil, 7]

[tree1.size, tree2.size].max.times.map { |i|
  tree1[i].nil? && tree2[i].nil? ? nil : tree1[i].to_i + tree2[i].to_i }
  #=> [3, 4, 5, 5, 4, nil, 7]    

Обратите внимание, что arr[i] #=> nil, если i >= arr.size и nil.to_i #=> 0.

Для читателей, незнакомых с использованием массива для хранения содержимого двоичного дерева (что составляет полчаса).назад, включая меня) Ниже я привел профессионально нарисованную картинку, которая показывает двоичные деревья, соответствующие трем массивам, приведенным в вопросе.

В каждом массиве узел с индексом i имеет левый узел с индексом 2*i+1 и правый узел с индексом 2*i+2.Например, в среднем массиве узел с индексом 0 (2) имеет свой левый узел (1) с индексом 2*0+1 #=> 1 и правый узел (3) с индексом 2*0+2 #=> 2.Аналогично, узел с индексом 1 (1) имеет правый узел (4) с индексом 2*1+2 #=> 3, но не имеет левого узла, поскольку элемент с индексом 2*1+1 #=> 3 равен nil.

* 1030.* Правило объединения двух двоичных деревьев: «Если два узла перекрываются (то есть узлы находятся на одной и той же позиции на обоих графиках), то суммируйте значения узлов как новое значение объединенного узла; в противном случае это узел, который являетсяподарок (не nil в связанном массиве) будет использоваться в качестве узла нового дерева. " ¹ Например, в объединенном дереве правый узел 3 5 равен 2 (из первого дерева) плюс 3 (из второго дерева), тогда как узел 7 взят из второго дерева, потому что у первого нет узла в этой позиции.

^{1,См. эту статью , в которой также обсуждаются алгоритмы объединения двоичных деревьев.}

Answer 3

a = [1,3,2,5]
b = [2,1,3,nil,4,nil,7]

small,big = [a,b].minmax
big.each_with_index.inject([]) do |merged, (el, idx)|
  merged << [el, small[idx]].instance_eval { compact.sum if any? }
end
#=> [3, 4, 5, 5, 4, nil, 7]