3

好的，我得到了一堆叶子 10,9,7,8，我需要从它们中创建一个总和树 在此处输入图像描述

我需要找到圈出的总和。

这个问题实际上是一个重量问题，我可以一次选择两个元素来添加它们，它们的组合权重是组合元素所做的工作，我必须继续这样做，直到所有权重组合在一起，同时做最少的量工作，但我把它变成了这个，因为我认为这是解决它的方法。

这是解决这个问题的最好方法还是有更好的方法？

创建这棵树并计算这些节点的总和的最快方法是什么？

4

3 回答 3

0

使用堆栈机。推叶子，直到堆栈有 2 个元素。弹出这些元素，添加（sub、mult、div 等）它们，然后推送结果。继续这样做，直到输入没有更多元素。最终结果在栈顶。该算法以和树相同的顺序进行算术运算。

code                stack
--------------------------
push 10             10$        
push 9              9, 10$     

pop a               10$
pop b               $
push a+b            19$

push 7              7, 19$
push 8              8, 7, 19$

pop a               7, 19$
pop b               19$
push a+b            15, 19$

pop a               19$
pop b               $
push a+b            34$

done                34$
于 2012-04-28T23:20:43.493 回答
0

贪婪的解决方案：

  1. 将所有叶子放入优先队列（首先出现最小权重）。
  2. 当队列包含多棵树时，拉出两棵最小权重的树，将它们连接起来，然后将联合树插入到队列中。
  3. 当队列仅包含一棵树时，这就是您的解决方案。

贪婪的解决方案有效：

给定从叶子构建的任何二叉树，每个叶子depth*weight都对总工作/成本做出贡献。（其中叶子的深度是从根到叶子的路径的长度，例如

   18
  /  \
  3   15
/  \ /  \
1  2 4  11
       / \
       5  6

叶子 1、2 和 4 的深度为 2，叶子 5 和 6 的深度为 3。）

因此，对于任何给定形状的树，当最轻的叶子最深时，总成本最小。因此，当第一步是将两个最轻的叶子连接到一棵新树时，就会达到最低成本树。

当一些叶子已经加入时，构建树的总成本是（到目前为止的成本）+（考虑非单棵树作为叶子的构建最便宜的树的成本）。

所以在最小成本树中，通过上面的推理，两个最轻的“叶子”必须在最深的层次，因此可以连接起来形成一个新的子树。

于 2012-04-28T23:29:32.113 回答
0

这是使用Java的实现

public static int sumTree(BinaryTreeNode<Integer> node) {
    if (node == null) {
        return 0;
    }
    int oldVal = node.getData();
    node.setData(sumTree(node.getLeft()) + sumTree(node.getRight()));

    return oldVal + node.getData();
}

这是测试用例

@Test
public void sumTreeTest() {
    BinaryTreeNode<Integer> bt = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{8,-2,-4,10,7,6,5}, new Integer[]{8,-4,-2,7,5,6,10});
    BinaryTreeUtil.sumTree(bt);
    List<Integer> result = new ArrayList<Integer>();
    BinaryTreeUtil.printInOrder(bt, result);
    assertThat(result.toArray(new Integer[0]), equalTo(new Integer[]{0, 4, 0, 20, 0, 12, 0}));
    //System.out.println(Arrays.toString(result.toArray()));
}
于 2016-04-06T16:28:13.273 回答