2

奇数の高さのノードの値の合計と偶数の高さのノードの値の合計の差を返す関数を作成するにはどうすればよいですか。バイナリ ツリーのルート ノードが高さ 1 にあると考えると、

入力：

                                      1
                              2                3
                          4        5       6        7
                      8     9  10    11  12  13   14  15

出力: -74 説明:

[ (1 + 4 + 5 + 6 + 7 ) - (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]

コード：

public static int diff(Node n) {
    if (n == null)
        return 0;
    return Sum(n) - Sum(n.left) - Sum(n.right);

}
public static int Sum(Node root) {
    int sum = 0;
    if (root == null) {
        return sum;
    }
    sum = sum + root.data;
    if (root.left != null) {
        sum = sum + Sum(root.left.left) + Sum(root.left.right);
    }
    if (root.right != null) {
        sum = sum + Sum(root.right.left) + Sum(root.right.right);
    }
    return sum;
}

私はこの解決策を提供しましたが、選択していません...これの何が問題なのかわかりません。

4

5 に答える 5

5 
public static int Sum(Node root) {

    if (root == null) {
        return 0;
    }
    return root.data-Sum(root.left)-Sum(root.right);
}

これは私が解決策を見つけた最も簡単で賢い方法です

于 2013-03-08T21:13:37.033 に答える
2

ここでの解決策は、再帰を使用して簡単に説明されています..

現在のレベル (現在のノードのレベル) の下のすべてのレベルを否定し、再帰の各ステップでそれを行います。

sum[l1] – (sum[l2] – (sum[l3] – (sum[l4] – … = sum[l1] – sum[l2] + sum[l3] – sum[l4]…

www.crazyforcode.com/binary-tree-diff-sum-even-nodes-sum-odd-nodes/

于 2013-07-29T14:52:26.190 に答える
1

どうですか...

public static int diff(Node n) {
    return sumtree(Node n, 1);
}

public static int sumtree(Node n, int level) {

   if (n == null) return 0;

   if (level % 2 == 0) { 
      return sumtree(n.left, level + 1) + sumtree(n.right, level +1 ) - n.value;
   } else {
      return sumtree(n.left, level + 1) + sumtree(n.right, level + 1) + n.value;
   }
}

奇数のレベル番号 (1、3、5 7...) で値を加算し、偶数 (2、4、6、8...) で値を減算します。

于 2012-11-16T19:43:27.220 に答える
0

私のソリューションをチェックしてください

traverse(root,1);  //1 is passed since we want oddlevelsum - evenlevelsum,pass -1 for opposite

int traverse(Tree* root,int level){

    if(root==NULL)return 0;
    return (level*root->data)+ traverse(level*-1,root->left_node)
       + traverse(level*-1,root->right_node);

}
于 2013-02-15T07:13:28.050 に答える
0

私が取ったアプローチは、最初にすべての葉を追加する方法を見つけることでした。次に、レベルが偶数の場合は「レベル係数」を追加し、それ以外の場合は減算します。これは他のものと似ているかもしれませんが、私はよりきれいだと思います。

ANSI C について

int diffOddAndEven(Node *root)
{
    return sumLevel(root, 0);
}

int sumLevel(Node *root, int level)
{
    int sum=0;
    int levelFactor = level%2 ? -1 : 1;

    if(!root)
        return 0;

    sum = root->value * levelFactor;

    sum += sumLevel(root->left, level+1);
    sum += sumLevel(root->right, level+1);

    return sum;
}
于 2012-12-14T16:55:23.163 に答える