c++ - 在二叉树中，找出有多少祖父只有两个或三个孙子

Question

                                   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++ 中有更优雅的方法来返回一对，但我将使用旧的笨拙的 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); }

这个函数同时做了两件事。简单的工作是它通过递增 *child_count 来帮助计算其 parent 的孙子，它还通过在 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; 
}