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）を呼び出すと、nullポインター例外エラーがスローされます。ノードの左右が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;
        }

    }
4

2 に答える 2

1

制御ステートメントelseはすべての場合に使用されるため、評価されるのは1つだけです。したがって、左側を評価する場合、戻ったときに右側を評価しません。

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 に答える
1

最後の例では、最後の「Else」を取り出し、前の条件の成功に関係なく合計を返すようにして、機能するはずです。

于 2010-07-13T20:08:12.087 に答える