检查二叉搜索树是否包含比奇数更多的偶数

Question

我想实现一个函数来检查 BST（整数值）是否包含更多 odds 它应该 return 2，如果它包含更多偶数 return 1 和 0 否则 - 递归。

我试图用偶数和奇数计数器的输入创建帮助函数，但是函数 return 输出错误。

我的代码：

int evenOdd(Tnode* root) {
    if (root == NULL)
        return 0 ;
    return eVenOddHelp(root , 0 , 0) ;
}

int eVenOddHelp(Tnode* root , int even , int odd) {
    if (root == NULL) {
        if (even > odd)
            return 1 ;
        else if (odd > even)
            return 2 ;
        return 0 ;
    }
    else {
        if (root->data % 2 == 0) {
            eVenOddHelp(root->left , even + 1 , odd) ;
            eVenOddHelp(root->right , even + 1 , odd) ;
        }
        else {
            eVenOddHelp(root->left , even , odd + 1) ;
            eVenOddHelp(root->right , even  , odd + 1) ;
        }
    }
}

Answer 1

IMO 最简单的方法是使用 return 值，如果 return 正则有更多 evens，如果负则有更多赔率，否则为0：

int evenOdd(Tnode* root) {
    int result = eVenOddHelp(root);
    if(result > 1) return 1;       // More evens
    else if(result == 0) return 0; // the same 
    else return 2;                 // More odds
}

int eVenOddHelp(Tnode* root) {
    if (root != NULL) {
       int isEven = (root->data % 2 == 0) ? 1 : -1;
       return eVenOddHelp(root->left) + eVenOddHelp(root->right) + isEven;
    }
    return 0;
}

这样比较：

if (root == NULL) {

    if (even > odd)
        return 1 ;
    else if (odd > even)

        return 2 ;
    return 0 ;

}

会产生错误的值，因为有几次 root == NULL 为真，您将比较不同子树中的偶数和赔率。而不是在整棵树的末尾。

Answer 2

通过使用作为可变指针传入的计数器，有一种更简单的方法可以做到这一点：

void modCounter(Tnode* node, int* even, int* odd) {
  if ((node->data % 2) == 0) {
    (*even)++;
  }
  else {
    (*odd)++;
  }

  if (node->left) {
    modCounter(node->left, even, odd);
  }

  if (node->right) {
    modCounter(node->right, even, odd);
  }
}

注意它只是改变了指向的值，所以你可以这样称呼它：

int evenOdd(Tnode* root) {
  if (root == NULL)
    return 0;

  int even = 0;
  int odd = 0;

  modCounter(root, &even, &odd);

  if (even > odd) {
    return 1;
  }

  if (odd > even) {
    return 2;
  }

  return 0;
}

要使用更基于 C 的方法，您甚至可以传入两个 int 值的数组，如：

void modCounter(Tnode* node, int* counters, int mod) {
  ++counters[node->data % mod];

  // ...
}

你在哪里这样称呼它：

int counters[2];

modCounter(root, &counters[0], 2);

检查二叉搜索树是否包含比奇数更多的偶数

Check if binary search tree contains more evens numbers than odds

c

algorithm

recursion

binary-search-tree