Geek asks and answers

Creating a tree of sums from leaves

ok I am given a bunch of leaves 10,9,7,8, and I need to create from them a sum tree as such enter image description here

I need to find the sum of what's around.

the problem really is a weight problem, where I can select two elements at a time to add them, and their total weight is the work done to combine the elements, and I must continue to do this until all the scales are combined while doing the minimum the amount of work, but I turned it into this because I think this is a way to solve it.

Is this the best way to solve this problem or is there a better way?

What would be the fastest way to create this tree and calculate the sum of these nodes?

+3
source share
3 answers

Greedy solution:

  • ( ).
  • , , .
  • , .

:

, , depth*weight /. ( - , ,

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

1, 2 4 2, 5 6 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$
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()));
}
0

More articles:


All Articles