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

这里的解决方案简而言之使用recurssion来解释..

否定当前级别（当前节点的级别）下的所有级别，然后在递归的每个步骤中执行此操作。

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

我采用的方法是首先找到一种添加所有叶子的方法，然后如果水平是你添加的水平，则只需添加一个“水平因子”，否则你减去。这可能看起来与其他人相似，但我觉得它更干净。

在 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 回答
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 回答