在二叉树中，找到有多少祖父只有两三个孙子

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

我需要找到一棵树的祖父，在这个例子中，我只有一个祖父，12号（我需要他只有两三个孙子）。

这是我到目前为止所尝试的：

 int T(struct node * tree){ int t = 0; if (tree == NULL) return 0; if (tree->left && tree->right) { //In this case i check if we NOT have all the four grandchildrens. if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right))) { t = 1 + T(tree->left) + T(tree->right); T(tree->left); T(tree->right); } else { T(tree->left); T(tree->right); } } return t; } 

不幸的是它不起作用……任何人都可以帮助我吗？

Answer 1

一种有效的方法是递归地返回一对结果。 有更优雅的方式在C ++中返回一对，但我将使用旧的kludgy C方式通过指针输入返回一个输出：

 int T2(struct node * tree, int* child_count) { int t = 0; // Count the things we are supposed to count int g = 0; // Count grandchildren of the current node if (tree == NULL) return 0; if ( tree->left ) { ++ *child_count; t += T2( tree->left, &g ); } if ( tree->right ) { ++ *child_count; t += T2( tree->right, &g ); } if ( g==2 || g==3 ) ++t; return t; } int T(struct node * tree) {int dummy; return T2(tree, &dummy); } 

该function共同完成两件事。 简单的工作是通过递增*child_count来帮助计算其父母的孙子，并且它还通过累积在t递归地完成主要工作。

---

以下方式可能更容易理解，但不太优雅：

 int T(struct node * tree) { struct node *c; int t = 0; // Count the things we are supposed to count int g = 0; // Count grandchildren of the current node if (tree == NULL) return 0; if ( (c=tree->left) != NULL ) { g += (c->left != NULL) + (c->right != NULL); t += T( c ); } if ( (c=tree->right) != NULL ) { g += (c->left != NULL) + (c->right != NULL); t += T( c ); } if ( g==2 || g==3 ) ++t; return t; } 

Answer 2

如果你引入一些儿童计数function，一个计算儿童的计数和一个计算孙子计数的function，这将变得更容易：

 int children(node* tree) { if (!tree) { return 0; } int count = 0; if (tree->left) { count += 1; } if (tree->right) { count += 1; } return count; } int grandchildren(node* tree) { if (!tree) { return 0; } return children(tree->left) + children(tree->right); } int grandparents(node* tree) { if (!tree) { return 0; } int count = grandchildren(tree); if (count == 2 || count == 3) { return 1 + grandparents(tree->left) + grandparents(tree->right); } else { return grandparents(tree->left) + grandparents(tree->right); } }