用于查找BST特定深度以下的节点数的函数

Question

我正在尝试创建一个函数，该函数将对大于特定深度“ k”的节点数进行计数。

这是我的遍历树的函数代码，以及用于查找每个节点深度的辅助函数的代码：

    int findDepth(BinaryNode * t, int value, int depth){

    if( t == nullptr ){
        return 0;
    }
    if( t->element == value){
        return depth;
    }
    int lowerDepth = findDepth(t->left, value, depth+1);

    if(lowerDepth != 0){
        return lowerDepth;
    }
    lowerDepth = findDepth(t->right, value, depth+1);

    return lowerDepth;

}

int countDeep( BinaryNode * t, int k ){
    int count = 0;
    if (t != nullptr){
        countDeep( t->left, k );
        if (findDepth(t, t->element, 0)){
            count++;
        }
        countDeep( t->right, k );
    }
    return count;
}

现在函数总是返回0，但我不太确定为什么。

Answer 1

考虑此：

int countDeep( BinaryNode * t, int k ){
    int count = 0;
    if (t != nullptr){
        countDeep( t->left, k );
        if (findDepth(t, t->element, 0)){
            count++;
        }
        countDeep( t->right, k );
    }
    return count;
}

我没有仔细阅读其他代码段，但是此函数返回0或1。因为您递归丢弃了它的返回值。此功能可以seen作为pure function（尽管您可以通过count修改++），所以在不使用其返回值的情况下调用它是错误的。

因此，如果另一个函数调用此函数，则该函数的count只有一次机会[，我没有检查您的代码，也许“仅机会”不存在，因为好。