用c语言求从二叉树根结点到指定结点p之间的路径

可以通过先序遍历二叉树，记录下经过的结点，当遍历到指定结点p时，即可得到从根结点到指定结点p的路径。

以下是C语言代码实现：

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

// 二叉树结点的定义
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 先序遍历二叉树
void preorder(TreeNode* root, TreeNode* p, TreeNode** path, int* pathSize, int* found) {
    if (root == NULL) return;

    // 将当前结点添加到路径中
    path[(*pathSize)++] = root;

    // 如果找到了指定结点p，则停止遍历
    if (root == p) {
        *found = 1;
        return;
    }

    // 遍历左子树
    preorder(root->left, p, path, pathSize, found);

    // 如果找到了指定结点p，则停止遍历
    if (*found) return;

    // 遍历右子树
    preorder(root->right, p, path, pathSize, found);

    // 如果找到了指定结点p，则停止遍历
    if (*found) return;

    // 如果当前结点既不是指定结点p，也没有左右子树可以遍历了，则将其从路径中移除
    (*pathSize)--;
}

// 获取从根结点到指定结点p的路径
TreeNode** getPath(TreeNode* root, TreeNode* p, int* pathSize) {
    // 如果根结点为空，则返回空路径
    if (root == NULL) {
        *pathSize = 0;
        return NULL;
    }

    // 创建一个数组，用于存储路径
    TreeNode** path = (TreeNode**)malloc(sizeof(TreeNode*) * 1000);

    // 初始化路径为空
    *pathSize = 0;

    // 是否已经找到了指定结点p
    int found = 0;

    // 先序遍历二叉树，获取从根结点到指定结点p的路径
    preorder(root, p, path, pathSize, &found);

    // 如果没有找到指定结点p，则返回空路径
    if (!found) {
        *pathSize = 0;
        free(path);
        return NULL;
    }

    return path;
}

使用示例：

int main() {
    // 创建一个二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;

    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
    node2->val = 2;

    TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
    node3->val = 3;

    TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
    node4->val = 4;

    TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode));
    node5->val = 5;

    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;
    node5->left = NULL;
    node5->right = NULL;

    // 获取从根结点到指定结点的路径
    TreeNode** path;
    int pathSize;
    TreeNode* p = node5;
    path = getPath(root, p, &pathSize);

    // 打印路径上的结点值
    for (int i = 0; i < pathSize; i++) {
        printf("%d ", path[i]->val);
    }

    return 0;
}

运行结果为：

1 2 5

表示从根结点到结点5的路径为1->2->5。