编写一个比较两棵树的函数，如果它们在结构和值上相等，则 returns 为真，否则为假

Question

给定两棵树，我想 return 如果它们在结构和值上相等则为真，否则为假。

给出以下 class：

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)

我的研究让我 here。我尝试了 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

如果 TreeNodes 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

首先，让我们修复 syntax/logic 错误：

使用括号强制执行运算符优先级：

while a,b = for_check.shift

应该是

while (a, b = for_check.shift)

当您尝试将元素推入其中时，数组 for_check 不存在。
```
for_check << [a, b]   
```
应该是
```
for_check = [a, b]   
```

其次，您的代码似乎与所提出的问题没有太大关系（尽管使用堆栈中的两个节点同时搜索是正确的想法）。首先，您在此处显示的 TreeNode class 没有 children 成员数组。该代码的目的是处理具有 n 个子节点的一般树并忽略这些子节点的顺序，这两个特征不属于您所面临的问题。

我的建议是重新解决问题，假设二叉树和子项的排序及其值很重要。

如果您想剧透，请尝试以下递归逻辑（迭代也可以，因为您正在使用显式堆栈，并且编写两者是有指导意义的）：

如果其中一个根为零，请确保另一个根也为零且return。我们要么在两棵树中都达到了零叶，这是有效的，要么一个是叶而另一个不是，这是无效的。这是基本情况。
如果两个根都非零，确保它们具有相同的值，然后递归验证左右子树。

代码如下：

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

例子

我们先创建两棵二叉树。它们将如下所示。

这些树在结构上看起来是相同的。

这是你的 class TreeNode.

class TreeNode
  attr_accessor :val, :left, :right

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

此外，我将创建一个class 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 returns 以下哈希值。

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

这些哈希是二叉树的 1-1 映射，即使它们的键顺序不同，它们显然是相等的。

编写一个比较两棵树的函数，如果它们在结构和值上相等，则 returns 为真，否则为假

Writing a function which compares two trees and returns true if they are equal in structure and in value and false otherwise

ruby

binary-tree

如果 TreeNodes a 和 b 在结构和值上相等，我希望输出为真，否则为假。