java - 如果树不完整，如何找到给定深度的节点值之和？

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)时，它会抛出空指针异常错误。我尝试添加逻辑来处理节点 left 和 right 为 null 的情况，但仍然不知道如何解决，如果不解决这个问题我就无法休眠..

有人能给我提示吗？我试过了，但不是，它只是返回 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

您的控制语句在每种情况下都使用 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 的机器上编写的。