这题跟dp啥关系啊?
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
currentSum = currentSum + node.key;
path.add(node);
if (node.left == null && node.right == null) {
if (currentSum < minSum) {
minSum = currentSum;
minPath.clear();
minPath.addAll(path);
}
return;
}
minSumPathFromRootToLeave(node.left, path, currentSum);
minSumPathFromRootToLeave(node.right, path, currentSum);
path.remove(node);
}
public void printMinSumPathFromRootToLeave() {
ArrayList path = new ArrayList();
int currentSum = 0;
minSumPathFromRootToLeave(root, path, currentSum);
for (BSTNode node : minPath) {
System.out.print(node.key + " ");
}
}