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

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，并且它还通过累积 来递归地完成主要工作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; 
}