0

我想以最低成本遍历二叉树，其中每条边的成本为 1。 当访问树的每个节点时，遍历就完成了。

例如，遍历后续树的最小成本是 13。

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

遍历后续树的最小成本为 12。

        *
       / \
      *   *
     / \   \
    *   *   *
   /     \
  *       *
 /
*
4

1 回答 1

7

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
于 2013-01-05T09:20:39.310 回答