草庐IT

java - 算法 - O(n) 中二叉搜索树的每两个节点之间的距离总和？

coder 2024-03-03 原文

问题是找出 BinarySearchTree 的每两个节点之间的距离之和，给定每个父子对由单位距离分隔。每次插入后都要计算。

例如:

 ->first node is inserted..

      (root)

   total sum=0;

->left and right node are inserted

      (root)
      /    \
  (left)   (right)

   total sum = distance(root,left)+distance(root,right)+distance(left,right);
             =        1           +         1          +         2
             =     4

and so on.....

我想到的解决方案:

  1. 蛮力。步骤:

    1. 执行 DFS 并跟踪所有节点:O(n)。
    2. 选择每两个节点并计算:O(nC2)_times_O(log(n))=O(n2log(n)) 它们之间的距离使用 Lowest Common Ancestor方法并将它们相加。

    总体复杂度:-O(n2log(n))。

  2. O(nlog(n))。步骤:-

    1. 在插入之前执行 DFS 并跟踪所有节点:O(n)。
    2. 计算插入节点和之间的距离:O(nlog(n))。其余节点。
    3. 将现有总和与第 2 步中计算的总和相加

    总体复杂度:-O(nlog(n))。

现在的问题是“是否存在 O(n) 阶的解？？

最佳答案

我们可以通过遍历树两次来做到这一点。

首先，我们需要三个数组

int []left 存储左子树的距离之和。

int []right 存储右子树的距离之和。

int []up 存储了父树(不包括当前子树)的距离之和。

所以，首先遍历，对于每个节点，我们计算左右距离。如果节点是叶子，简单地返回 0，如果不是，我们可以有这个公式:

int cal(Node node){
    int left = cal(node.left);
    int right = cal(node.right);
    left[node.index] = left;
    right[node.index] = right;
    //Depend on the current node have left or right node, we add 0,1 or 2 to the final result
    int add = (node.left != null && node.right != null)? 2 : node.left != null ? 1 : node.right != null ? 1 : 0;
    return left + right + add;
}

然后对于第二次遍历，我们需要向每个节点添加与其父节点的总距离。

             1
            / \
           2   3
          / \
         4   5

例如，对于节点1(根)，总距离为left[1] + right[1] + 2，up[1] = 0； (我们加 2 是因为根节点有左右子树，具体公式为:

int add = 0; 
if (node.left != null) 
    add++;
if(node.right != null)
    add++;

对于节点 2 ，总距离是 left[2] + right[2] + add + up[1] + right[1] + 1 + addRight, up[2 ] = up[1] + right[1] + addRight.之所以在公式末尾有一个1，是因为当前节点到他的父节点有一条边，所以我们需要加上1。现在，我表示当前节点的附加距离是 add，如果父节点中有左子树，则附加距离是 addLeft 类似地 addRight 对于右子树。

对于节点3，总距离为up[1] + left[1] + 1 + addLeft, up[3] = up[1] + left[1] +添加左边;

对于节点4，总距离为up[2] + right[2] + 1 + addRight, up[4] = up[2] + right[2] +添加权利;

因此根据当前节点是左节点还是右节点，我们相应地更新up。

时间复杂度是O(n)

关于java - 算法 - O(n) 中二叉搜索树的每两个节点之间的距离总和？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24793567/

java的coderightleftalgorithmtime-complexitybinary-search-treedynamic-programming

有关java - 算法 - O(n) 中二叉搜索树的每两个节点之间的距离总和？的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  3. 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/

  4. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  5. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  6. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  7. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  8. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  9. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  10. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

随机推荐