ruby - 如何在 ruby​​ 中合并两个二叉树？

Question

我有 2 棵二叉树 [1,3,2,5] 和 [2,1,3,null,4,null,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

标签： rubyalgorithm

Answer 1

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。

对于不熟悉使用数组存储二叉树内容的读者（半小时前，包括我在内），我在下面提供了一张专业绘制的图片，该图片显示了与给出的三个数组对应的二叉树这个问题。

在每个数组中， index 处的节点在 index 处i有一个左节点，在 index处有2*i+1一个右节点2*i+2。例如，在中间数组中，位于 index 0( 2) 处的节点的左节点 ( 1) 位于 index 处2*0+1 #=> 1，其右节点 ( 3) 位于 index 处2*0+2 #=> 2。类似地，index() 处的节点在 index 处1有1一个右节点 ( 4) 2*1+2 #=> 3，但没有左节点，因为 index 处的元素2*1+1 #=> 3是nil。

合并两棵二叉树的规则是：“如果两个节点重叠（即节点在两个图中的位置相同），则将节点值相加作为合并节点的新值；否则，存在的节点（不在nil关联数组中）将用作新树的节点。” ¹例如，在合并树中， node3的右节点5等于2（来自第一棵树）加上3（来自第二棵树），而 node7取自第二棵树，因为第一棵树在该位置没有节点。

^{1. 见这篇文章，它还讨论了合并二叉树的算法。}