0

二分木のパス長を計算する関数を実装しようとしていますが、正しい答えを得ることができません。私が間違っていることを確認できますか？以下は私のコードです：

public int pathLength() {
    int sum = 0;
    int c = 1;
    pathLength(root, sum);
    return sum;
}

public int pathLength(Node n, int sum) {
    if(n.isRoot())
        sum+= 0;
    if(n.left == null && n.right == null)
        return;
    c++;
    if(n.left != null)
        sum += c;
    if (n.right != null)
        sum+=c;
    pathLength(n.left, sum);
    pathLength(n.right, sum); 

}
4

3 に答える 3

1

このコードには多くの問題があります。a) 2 番目の関数では c が宣言されず (最初の関数ではローカル)、b) 2 番目の関数が値を返さないため、コンパイルすらできません。

しかし、最大の問題は、2 番目の関数を宣言する方法です。「合計」は値渡しです。これは基本的に、関数を呼び出すたびに「sum」の新しいコピーが作成され、関数が終了すると破棄されることを意味します。

あなたがしたいことは、参照渡しです。これを行うと、コピーではなく実際の合計変数が関数に渡されます。したがって、コードは次のようになります。

public void pathLength(Node n, int& sum) {
    //if(n.isRoot())     <- not sure what this is for
    //    sum+= 0;

    sum += 1;   // Increment for this node

    //if(n.left == null && n.right == null)
    //    return;      // This conditional is not needed with next 2 if statements

    //c++;    <- Don't know what c is for

    // Recursively call for child nodes
    if(n.left != null)
        pathLength(n.left, sum);
    if (n.right != null)
        pathLength(n.right, sum); 
}

これにより、ツリー内のすべてのノードがカウントされることに注意してください。それがあなたの望むものだと思います。最も深いノードを見つけたい場合、それは異なります。

于 2012-11-17T06:02:37.833 に答える