- 145.5k
- 22
- 190
- 479
package binarytree;
public class Node {
public final int weight;datum;
public final Node left, right;
public Node(int weightdatum, Node left, Node right) {
this.weightdatum = weight;datum;
this.left = left;
this.right = right;
}
public Node(int weightdatum) {
this(weightdatum, null, null);
}
}
public class HeaviestPath {
private HeaviestPath() {}
/**
* JavaDoc here
*/
public static int weight(Node root) {
if (root == null) {
return 0;
} else {
return root.datadatum + Math.max(weight(root.left), weight(root.right));
}
}
}
package binarytree;
public class Node {
public final int weight;
public final Node left, right;
public Node(int weight, Node left, Node right) {
this.weight = weight;
this.left = left;
this.right = right;
}
public Node(int weight) {
this(weight, null, null);
}
}
public class HeaviestPath {
private HeaviestPath() {}
/**
* JavaDoc here
*/
public static int weight(Node root) {
if (root == null) {
return 0;
} else {
return root.data + Math.max(weight(root.left), weight(root.right));
}
}
}
package binarytree;
public class Node {
public final int datum;
public final Node left, right;
public Node(int datum, Node left, Node right) {
this.datum = datum;
this.left = left;
this.right = right;
}
public Node(int datum) {
this(datum, null, null);
}
}
public class HeaviestPath {
private HeaviestPath() {}
/**
* JavaDoc here
*/
public static int weight(Node root) {
if (root == null) {
return 0;
} else {
return root.datum + Math.max(weight(root.left), weight(root.right));
}
}
}
The algorithm looks sound. It visits every node once, and cannot be more efficient than that.
I find it odd that you split the code into two classes, one of which is non-public. Since the Node class is non-public, no code in any other package will be able to construct a Node. The algorithm is therefore "unusable".
There are two ways to model a tree: a "lazy" way (exposing the nodes, and a tree is just referred to by its root node) and a "polished" way (with the tree being an opaque data structure that hides and manages its nodes). Here, you have an odd hybrid.
If you want to have a BinaryTree class that contains nothing but a static method, then you should suppress the implicit no-argument default BinaryTree() constructor by making it private:
public class BinaryTree {
// Suppress the default constructor
private BinaryTree() {}
public static int getHeaviestPathWeight(...) {
...
}
}
Package names are conventionally all lowercase.
Whenever possible, use int instead of Integer. Using Integer objects is less efficient and usually results in more complicated source code and bytecode. One reason why you might need an Integer instead of an int would be to store a null — and that sounds more like a liability than an advantage in this case.
To language purists, "data" is plural, and "datum" is singular. However, I would suggest a different name altogether, such as weight.
Simple solution
package binarytree;
public class BinaryTree {
private final int weight;
private final BinaryTree left, right;
public BinaryTree(int weight, BinaryTree left, BinaryTree right) {
this.weight = weight;
this.left = left;
this.right = right;
}
public BinaryTree(int weight) {
this(weight, null, null);
}
/**
* JavaDoc here
*/
public int getHeaviestPathWeight() {
return this.weight + Math.max(
this.left == null ? 0 : this.left.getHeaviestPathWeight(),
this.right == null ? 0 : this.right.getHeaviestPathWeight()
);
}
}
Alternate solution
package binarytree;
public class Node {
public final int weight;
public final Node left, right;
public Node(int weight, Node left, Node right) {
this.weight = weight;
this.left = left;
this.right = right;
}
public Node(int weight) {
this(weight, null, null);
}
}
public class HeaviestPath {
private HeaviestPath() {}
/**
* JavaDoc here
*/
public static int weight(Node root) {
if (root == null) {
return 0;
} else {
return root.data + Math.max(weight(root.left), weight(root.right));
}
}
}