Написание функции, которая сравнивает два дерева и возвращает true, если они равны по структуре и значению, и false в противном случае

Question

Учитывая два дерева, я хочу вернуть true, если они равны по структуре и значению, и false в противном случае.

Учитывая следующий класс:

class TreeNode
  attr_accessor :val, :left, :right

  def initialize val, left = nil, right = nil
    @val = val
    @left = left
    @right = right
  end
end

завершить функцию

def binary_tree_compare(a, b)

Мои исследования привели меня к здесь .Я пробовал решение ruby, но безрезультатно Ниже приведен код, который я пробовал до сих пор:

def binary_tree_compare a, b
  for_check << [a, b]   

  while a,b = for_check.shift  
    return false unless a.children.count == b.children.count 
    break if a.children.empty?

    a_children = a.children.sort 
    b_children = b.children.sort     
    return false unless a_children == b_children  

    0.upto(a_children.count - 1) do |i|
      for_check << [a_children[i], b_children[i]]  
    end
  end
  return true
end

Я ожидаю, что вывод будет истинным, если узлы TreeNode a и b равны по структуре, а также по значению и ложномув противном случае.

Я получаю синтаксическую ошибку, и это трассировка стека:

  solution.rb:4: syntax error, unexpected ',', expecting keyword_do_cond or ';' or '\n'
    while a,b = for_check.shift  
           ^
  solution.rb:12: syntax error, unexpected keyword_do_cond, expecting keyword_end
  ...0.upto(a_children.count - 1) do |i|
  ...                             ^~
  olution.rb:15: syntax error, unexpected keyword_end, expecting end-of-input
    end
    ^~~ ```

Answer 1

Во-первых, давайте исправим синтаксические / логические ошибки:

1. Используйте скобки для обеспечения приоритета оператора:

   while a,b = for_check.shift
   

   должно быть

   while (a, b = for_check.shift)
   

2. Массив for_check не существует, когда вы пытаетесь вставить в него элемент.

   for_check << [a, b]   
   

   должно быть

   for_check = [a, b]   
   

Во-вторых, ваш код, похоже, не имеет большого отношения к представленной проблеме (хотя одновременный поиск с использованием обоих узлов в стеке - правильная идея). Например, класс TreeNode, который вы здесь показали, не имеет массива children. Целью этого кода является обработка общих деревьев с n потомками, а также игнорирование упорядочения этих потомков, двух характеристик, которые не являются частью проблемы, с которой вы сталкиваетесь.

Моя рекомендация - переосмыслить проблему, предполагая, что двоичное дерево и порядок дочерних элементов имеют значение, а также их значения.

Если вы хотите использовать спойлер, попробуйте следующую рекурсивную логику (итеративная работа также работает, как вы делаете с явным стеком, и это полезно для написания обоих):

1. Если один из корней равен nil, убедитесь, что другой корень также равен nil, и вернитесь. Мы либо достигли взаимно нулевых листьев в обоих деревьях, что является допустимым, либо один является листом, а другой - нет, что недопустимо. Это базовый случай.
2. Если оба корня не равны нулю, убедитесь, что они имеют одинаковое значение, а затем рекурсивно проверяют как левое, так и правое поддеревья.

Вот код:

class TreeNode
  attr_accessor :val, :left, :right

  def initialize val, left = nil, right = nil
    @val = val
    @left = left
    @right = right
  end
end

def binary_tree_compare a, b
  return !a && !b if !a || !b
  return false if a.val != b.val
  return binary_tree_compare(a.left, b.left) &&
         binary_tree_compare(a.right, b.right)
end

a = TreeNode.new(
  1, TreeNode.new(
    2, TreeNode.new(4)
  ), TreeNode.new(3)
)
b = TreeNode.new(
  1, TreeNode.new(
    2, TreeNode.new(4)
  ), TreeNode.new(3)
)

puts binary_tree_compare a, b

Answer 2

Код

def binary_tree_compare(a_top_node, b_top_node)
  convert(a_top_node) == convert(b_top_node)
end

def convert(node)
  { node.val => recurse(node) }
end

def recurse(node)
  return nil if node.left.nil? && node.right.nil?
  [node.left, node.right].each_with_object({}) do |n, h|
    h[n.val] = recurse(n) unless n.nil?
  end
end

Пример

Давайте сначала создадим два двоичных дерева. Они будут выглядеть следующим образом.

Эти деревья имеют одинаковую структуру.

Это ваш класс TreeNode.

class TreeNode
  attr_accessor :val, :left, :right

  def initialize val, left = nil, right = nil
    @val = val
    @left = left
    @right = right
  end
end

Кроме того, я создам класс Tree.

class Tree
  attr_reader :top_node, :name_to_node

  def initialize(top_node_name)
    @top_node = TreeNode.new(top_node_name)
    @name_to_node = { top_node_name=>@top_node }
  end

  def add_node(name, parent, side)
    node = TreeNode.new(name)
    name_to_node[name] = node
    if side == :left
      name_to_node[parent].left = node
    else
      name_to_node[parent].right = node
    end
  end
end

Теперь мы можем построить два двоичных дерева, показанных на рисунке.

a = Tree.new(1)
a.add_node(2, 1, :left)
a.add_node(3, 1, :right)
a.add_node(4, 2, :left)
a.add_node(5, 3, :right)

a.top_node
  #=> #<TreeNode:0x000059e97fa499e0 @val=1,
  #     @left=#<TreeNode:0x000059e97fa508d0 @val=2,
  #       @left=#<TreeNode:0x000059e97fa719b8 @val=4, @left=nil, @right=nil>,
  #       @right=nil>,
  #     @right=#<TreeNode:0x000059e97fa66900 @val=3,
  #       @left=nil,
  #       @right=#<TreeNode:0x000059e97fa7cb60 @val=5, @left=nil, @right=nil>>> 

b = Tree.new(1)
b.add_node(2, 1, :right)
b.add_node(3, 1, :left)
b.add_node(4, 2, :right)
b.add_node(5, 3, :left)

b.top_node
  #=> #<TreeNode:0x000059e97fa99b48 @val=1,
  #     @left=#<TreeNode:0x000059e97fab5758 @val=3,
  #       @left=#<TreeNode:0x000059e97faf4cf0 @val=5, @left=nil, @right=nil>,
  #       @right=nil>,
  #     @right=#<TreeNode:0x000059e97faaf9e8 @val=2,
  #       @left=nil,
  #       @right=#<TreeNode:0x000059e97fac0040 @val=4, @left=nil, @right=nil>>> 

Теперь определите, равны ли эти два двоичных дерева по структуре.

binary_tree_compare(a.top_node, b.top_node)
  #=> true

Объяснение

convert возвращает следующие хэши.

convert(a.top_node)
  #=> {1=>{2=>{4=>nil}, 3=>{5=>nil}}} 
convert(b.top_node)
  #=> {1=>{3=>{5=>nil}, 2=>{4=>nil}}}

Эти хэши, которые являются 1-1 отображениями двоичных деревьев, явно равны, даже если их ключи не в том же порядке.