草庐IT

java - 二叉树是否包含另一棵树？

coder 2024-03-14 原文

好吧伙计们，我在今天的采访中被问到了这个问题，它是这样的:

“判断一棵二叉树是否包含在另一棵二叉树中(包含意味着节点的结构和值)”

我想到了以下方法:

将较大的树展平为:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}

(我确实为此编写了代码，{-} 表示空的左子树或右子树，每个子树都包含在 {} 括号内)

现在对于较小的子树，我们需要匹配这个模式:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}

其中 {.*} 表示一个空的或非空的子树。

当时我想，这将是 java 中一个微不足道的正则表达式模式匹配问题，但我被蒙蔽了。其实现在我觉得，我只是转换了问题(从另一个怪物中创造出一个怪物)。

是否有一个简单的正则表达式来匹配这些模式？我知道可能有其他方法可以解决这个问题，而这可能不是最好的方法。我只是想知道这是否可以解决。

最佳答案

我不确定面试官所说的“包含在另一棵二叉树中”到底是什么意思。如果面试官问的是检查 A 是否是 B 的子树的方法，这里有一个完全不需要正则表达式的方法:

  • 使用前序遍历将树 A 和 B 展平以获得字符串，例如 preA 和 preB
  • 使用中序遍历将树 A 和 B 展平以获得字符串，例如 inA 和 inB
  • 确保在字符串中也包含空叶(例如使用空格)
  • 检查 preA 是否是 preB 的子串并且 inA 是否是 inB 的子串

之所以要包含空叶子，是因为当多个节点具有相同的值时，前序和中序可能不够用。这是一个例子:

          A
      A       A
   B     B       C
 C         D       B
D           C       D

你也可以看看这个:

checking subtrees using preorder and inorder strings

另请阅读此内容以获取有关二叉树的前序和中序遍历的更多信息:

http://en.wikipedia.org/wiki/Tree_traversal

现在，如果他的意思不仅仅是子树，那么问题可能会变得更加复杂，具体取决于面试官所说的“部分”是什么意思。您可以将问题视为子图同构问题(树只是图的子集)，这是 NP 完全问题。

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

可能有更好的方法，因为树比图更受限制和更简单。

关于java - 二叉树是否包含另一棵树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18319439/

java二叉树sectioncode展平regexbinary-treepuzzle

有关java - 二叉树是否包含另一棵树？的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  3. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  4. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  5. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  6. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  7. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  8. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

  9. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

  10. ruby - 在 Windows 机器上使用 Ruby 进行开发是否会适得其反？ - 2

    这似乎非常适得其反，因为太多的gem会在window上破裂。我一直在处理很多mysql和ruby​​-mysqlgem问题(gem本身发生段错误，一个名为UnixSocket的类显然在Windows机器上不能正常工作，等等)。我只是在浪费时间吗？我应该转向不同的脚本语言吗？ 最佳答案 我在Windows上使用Ruby的经验很少，但是当我开始使用Ruby时，我是在Windows上，我的总体印象是它不是Windows原生系统。因此，在主要使用Windows多年之后，开始使用Ruby促使我切换回原来的系统Unix，这次是Linux。Rub

随机推荐