1

我之前问过非常相似的问题，应该更详细地提到。上次是 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
         *           
         */

因此，当我调用 7+9 的 getNodeValueByDepth(root, 3) 时，它会抛出空指针异常错误。我尝试添加逻辑来处理节点左右为空但仍然无法弄清楚如何并且如果不解决这个问题我就无法入睡的情况。

谁能给我一个提示？我试过但不是它只返回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;
        }

    }
4

2 回答 2

1

在最后一个示例中，取出最后一个“Else”，无论前面的条件是否成功，都让它返回总和，它应该可以工作。

于 2010-07-13T20:08:12.087 回答
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 的机器上写的。

于 2010-07-13T20:07:18.173 回答