Как найти сумму значения узла для заданной глубины, если дерево НЕ завершено?

Question

Я задавал очень похожий вопрос раньше и должен был упомянуть более подробно. В прошлый раз было «как найти сумму значения узла для заданной глубины в двоичном дереве» в 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 (root, 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;
        }

    }

Answer 1

В последнем примере выньте последний «Остальное», пусть он вернет сумму независимо от успешности предыдущих условий, и она должна работать.

Answer 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.