algorithm - 遍历二叉树的最小代价是多少

Question

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

例如，遍历树的最小代价是13。

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

遍历树的最小代价是12。

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

Answer 1

遍历树的成本是n-1，其中n是节点数。

这是真的，因为每棵树都有恰好 n-1 条边 - 您需要使用所有边才能访问所有节点。

---

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

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