Ad

# Untitled

unknown
java
a year ago
3.1 kB
2
Indexable
Never
package ee.ttu.algoritmid.subtreesum;

public class SubtreeSum {

/**
* Calculate sum of all right children for every node
* @param rootNode root node of the tree. Use it to traverse the tree.
* @return root node of the tree where for every node is computed sum of it's all right children
*/
public Node calculateRightSums(Node rootNode) {

sumOfRightLeaves(rootNode);
return rootNode;

}
public static long sumOfRightLeaves(Node rootNode) {

// Kui juur on null
if (rootNode == null)
return 0;
// Kui juure vasak ja parem node on null, eksisteerib ainult juur
if (rootNode.getLeft() == null && rootNode.getRight() == null)
return rootNode.getValue();

// Uuenda vasakut ja paremat alampuud rekursiooniga (funktsioon kutsub iseennast uuesti välja)
long rightSum = sumOfRightLeaves(rootNode.getRight());
long leftSum = sumOfRightLeaves(rootNode.getLeft());

// Lisa praegusele nodele rightSum
rootNode.setSumOfAllRight(rightSum);

// Väljasta juurealuste nodede summa
return rootNode.getSumOfAllRight() + leftSum + rootNode.getValue();
}
public static void printNodesWithRightSums(Node node)
{
// Kui juur on null
if (node == null) {
return;
}

//System.out.printf("(%d) : ", node.getValue());

//Väljasta vasakult paremale juured ja nende parempoolsete alampuude summa
printNodesWithRightSums(node.getLeft());

System.out.printf("(%d)-> ", node.getValue());
System.out.print(node.getSumOfAllRight() + ", ");

printNodesWithRightSums(node.getRight());
}

public static void main(String[] args) throws Exception {
/**
*  Use this example to test your solution
*                  Tree:
*                   15
*               /       \
*             10         17
*           /   \       /  \
*         3     13     5    25
*/
Node rootNode = new Node(15);
Node a = new Node(10);
Node b = new Node(17);
Node c = new Node(3);
Node d = new Node(13);
Node e = new Node(5);
Node f = new Node(25);

rootNode.setLeft(a);
rootNode.setRight(b);
a.setLeft(c);
a.setRight(d);
b.setLeft(e);
b.setRight(f);

SubtreeSum solution = new SubtreeSum();
solution.calculateRightSums(rootNode);

if (rootNode.getSumOfAllRight() != 47 ||
a.getSumOfAllRight() != 13 ||
b.getSumOfAllRight() != 25 ||
c.getSumOfAllRight() != 0) {
throw new Exception("There is a mistake in your solution.");
}

System.out.println("Your solution should be working fine in basic cases, try to push.");

printNodesWithRightSums(rootNode);
}

}

Ad