如何从IPL函数中获得精确值？

Question

#include <stdio.h>
#include <stdlib.h>

typedef struct treeNode {
    int key;
    struct treeNode* left;
    struct treeNode* right;
} treeNode;


int count = 0;

treeNode* insertNode(treeNode** t1, int x) {
    if (*t1 == NULL) {
        *t1 = malloc(sizeof(treeNode));
        (*t1)->key = x;
        (*t1)->left = NULL;
        (*t1)->right = NULL;
    }
    else if (x < (*t1)->key) {  //left
        (*t1)->left = insertNode(&(*t1)->left, x);
    }
    else if (x > (*t1)->key) { //right
        (*t1)->right = insertNode(&(*t1)->right, x);
    }
    else {
        printf("SameValue exist.\n");
    }
    return *t1;
}

int getIPL(treeNode* n1) {
    int rightcount;
    int leftcount;
    int rootcount = 1;

    if (n1 != NULL) {
        if (n1->left == NULL && n1->right == NULL) {
            count = rootcount;
        }
        else if (n1->left != NULL && n1->right == NULL) {
            leftcount = 1 + getIPL(n1->left);
            count += leftcount;
        }
        else if (n1->left == NULL && n1->right != NULL) {
            rightcount = 1 + getIPL(n1->right);
            count += rightcount;
        }
        else {
            leftcount = 1 + getIPL(n1->left);
            rightcount = 1 + getIPL(n1->right);
            count += leftcount + rightcount;
        }
    }
    return count;
}


int main() {
    treeNode* T1 = NULL;

    insertNode(&T1, 10);
    insertNode(&T1, 20);
    insertNode(&T1, 3);
    insertNode(&T1, 25);

    printf("IPL : %d", getIPL(T1));
}

此代码用于从BST获取内部路径长度(IPL)。它通常工作到2级，但在2级以上就不能工作了。

当放在树10 5 15上时，IPL值为5。

之后，加上30，你会得到9，而不是正常的值8。

我想要IPL值为8。

请告诉我问题出在哪里。

Answer 1

需要考虑每个节点的深度。例如：

static int getIPL_helper(treeNode *n1, int depth) {
    if (n1) {
        return getIPL_helper(n1->left, depth + 1) +
               getIPL_helper(n1->right, depth + 1) + depth;
    } else {
        return 0;
    }
}

int getIPL(treeNode *n1) {
    return getIPL_helper(n1, 1);
}