Как найти сумму значения узла для данной глубины, ЕСЛИ дерево не завершено?
Я задал очень похожий вопрос прежде и должен был упомянуть более подробный. Прошлый раз был, "как найти сумму значения узла для данной глубины в двоичном дереве" в PHP.
sum(Node, Level) =
if (Level == 0) return Node.value;
else return f(Node.left, Level-1) +
f(Node.right, Level-1).
Таким образом, теперь я пытался записать это в Java. И Java бросает nullPointerException. Причина состоит в том, потому что код ниже не обрабатывает в случае, если дерево не завершено.
public int getNodeValueByDepth(Node n, int level) {
if(level == 0) {
return n.data;
}
else {
return getNodeValueByDepth(n.left, level-1) +
getNodeValueByDepth(n.right, level-1);
}
}
Моя тестовая древовидная структура:
/*
* construct tree
* sum of node's value
* 5 depth 0 ==> 5
* / \
* 3 10 depth 1 ==> 13
* / \ / \
* 2 4 6 11 depth 2 ==> 23
* / \
* 7 9 depth 3 ==> 16
*
* depth 4 ==> null
*
*/
Таким образом, когда я называю getNodeValueByDepth (корень, 3), который является 7+9, он бросает и ошибка исключения нулевого указателя. Я пытался добавить логику для обработки случая, где левый и правый узел является пустым, но все еще не может выяснить, как и я не могу спать, не решая это..
Кто-либо мог дать мне подсказку? Я попробовал, но не это просто возвращается 0.
public int getNodeValueByDepth(Node n, int level) {
int sum = 0;
if(level == 0) {
return sum + n.data;
}
else if(n.left != null) {
return sum += getNodeValueByDepth(n.left, level-1);
}
else if(n.right != null) {
return sum += getNodeValueByDepth(n.right, level-1);
}
else {
return sum + 0;
}
}
2 ответа
Ваши управляющие операторы используют else в каждом случае, поэтому только один когда-либо получает оценку. Таким образом, если он оценивается для левой стороны, то при возврате он не выполняет правую сторону.
public int getNodeValueByDepth(Node n, int level) {
int sum = 0;
/** If we have reached our desired level */
if (level == 0) {
if (n != null) {
/** Assuming data is an int and not nullable */
return n.data;
} else {
/** Change this to 0 if you don't want an error condition */
return -1;
}
/** We are not the desired level, so get the sum of .left and .right, knowing either may not exist */
if (n.left != null) {
sum += getNodeValueByDepth(n.left, level-1);
}
if (n.right != null) {
sum += getNodeValueByDepth(n.right, level-1);
}
/** Now have evaluated every possible child and stored the sum, even if it is 0 */
return sum;
}
Примечание: Проверьте синтаксические ошибки, я писал это на машине без Java.
В последнем примере выньте последнее «Иначе», пусть оно вернет сумму независимо от успеха предыдущих условий, и это должно сработать.