遍历二叉树的最低成本是多少

Question

我希望以最低成本遍历二叉树,其中每个边的成本为1. 当访问树的每个节点时,遍历完成.

例如,跟随树的遍历的最低成本是13.

       *
      / \
     *   *
    / \   \
   *   *   *
  /   /     \
 *   *       *

跟随树的遍历的最低成本是12.

        *
       / \
      *   *
     / \   \
    *   *   *
   /     \
  *       *
 /
*

Answer 1

遍历树的成本是n-1其中n的节点的数量.

这是真的,因为每棵树都有完全的n-1边 - 你需要使用它们才能访问所有节点.

确切地说,已知接下来的3个语句对于具有节点的图 是等效的:Tn

1. T是一棵树(没有循环连接)
2. T连接并具有n-1个边缘
3. T没有周期并且具有n-1个边缘

从上面我们可以得出结论,在树中,为了到达所有节点,我们必须使用所有边(因为没有循环,所以没有冗余边) - 并且确实存在n-1这些边.

编辑:

从你的例子来看,你似乎也计算从每个边缘返回的时间(即一些边缘被计算两次).

那么,在这种情况下,最佳解决方案将是:

cost = (n-1)*2 - height

说明/校对指南: 树中完全
有n-1边.除了从根到最深节点的那些之外,它们中的每一个都被遍历两次.
您必须使用每个边缘(除了提到的)两次,因为除了最后一个分支 - 您从每个节点返回.
由于height最后一个分支中存在完全边缘,因此总计得到cost = (n-1)*2 - height

请注意,它与您的基本相同:

height + 2*(n-1-height) = height + 2(n-1) -2height = 2(n-1) - height