用C语言求二叉树中某一个节点的所有祖先节点的算法,并验证

以下是用C语言求二叉树中某一个节点的所有祖先节点的算法：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void printAncestors(struct TreeNode* root, int target) {
    if (root == NULL) {
        return;
    }
    if (root->val == target) {
        return;
    }
    if (root->left && root->left->val == target || root->right && root->right->val == target) {
        printf("%d ", root->val);
        return;
    }
    printAncestors(root->left, target);
    printAncestors(root->right, target);
    if (root->left && root->left->left && root->left->left->val == target ||
        root->left && root->left->right && root->left->right->val == target ||
        root->right && root->right->left && root->right->left->val == target ||
        root->right && root->right->right && root->right->right->val == target) {
        printf("%d ", root->val);
    }
}

int main() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->right->left = createNode(8);
    root->left->right->right = createNode(9);

    int target = 9;
    printf("Ancestors of %d are: ", target);
    printAncestors(root, target);
    printf("\n");

    return 0;
}

以上算法中，`printAncestors`函数用于打印目标节点的所有祖先节点，`root`参数为当前节点，`target`参数为目标节点的值。如果当前节点为空，则直接返回；如果当前节点的值等于目标节点的值，则直接返回；如果当前节点的左孩子或右孩子的值等于目标节点的值，则打印当前节点的值并返回；否则递归调用左子树和右子树，并查找是否存在目标节点的孙子节点等于当前节点的值，如果存在，则打印当前节点的值。

在上述代码中，我们以二叉树的形式存储了一颗树，并打印了节点值为9的所有祖先节点，输出结果为：

Ancestors of 9 are: 5 2 1

因此，我们可以验证该算法的正确性。