C++求二叉树指定结点到根节点的路径

二叉树的每个结点都有两个指针，指向其左、右子树，可以使用递归的方式来求解指定结点到根节点的路径。

具体步骤如下：

1. 如果当前结点为空，则返回false。

2. 如果当前结点为目标结点，则返回true。

3. 递归遍历左子树，如果左子树中存在目标结点，则将当前结点加入路径中，并返回true。

4. 递归遍历右子树，如果右子树中存在目标结点，则将当前结点加入路径中，并返回true。

5. 如果左、右子树都不存在目标结点，则返回false。

6. 如果返回true，则将当前结点加入路径中。

7. 返回路径。

下面是C语言实现代码：

#include <stdio.h>
#include <stdbool.h>

// 二叉树结点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 递归求解路径
bool findPath(struct TreeNode* root, int target, int* path, int* pathLen) {
    // 如果当前结点为空，则返回false
    if (root == NULL) {
        return false;
    }

    // 如果当前结点为目标结点，则返回true
    if (root->val == target) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 递归遍历左子树
    if (findPath(root->left, target, path, pathLen)) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 递归遍历右子树
    if (findPath(root->right, target, path, pathLen)) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 如果左、右子树都不存在目标结点，则返回false
    return false;
}

// 求解指定结点到根节点的路径
int* getPath(struct TreeNode* root, int target, int* returnSize) {
    // 定义路径数组
    int* path = (int*)malloc(1000 * sizeof(int));

    // 定义路径长度
    int pathLen = 0;

    // 递归求解路径
    findPath(root, target, path, &pathLen);

    // 将路径数组反转，得到从根节点到指定结点的路径
    int i, j;
    for (i = 0, j = pathLen - 1; i < j; i++, j--) {
        int temp = path[i];
        path[i] = path[j];
        path[j] = temp;
    }

    // 设置返回值
    *returnSize = pathLen;

    // 返回路径数组
    return path;
}

使用方法如下：

int main() {
    // 构建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 求解路径
    int* path;
    int pathLen;
    path = getPath(root, 4, &pathLen);

    // 输出路径
    int i;
    for (i = 0; i < pathLen; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");

    return 0;
}

输出结果为：3 4