C语言算法-解答路径总和 II算法问题的C语言实现

题目

给定一颗二叉树和一个整数目标值，找出所有从根节点到叶子节点的路径，这些路径上节点值的总和等于目标值。

引言

二叉树路径总和问题是一个常见的二叉树问题，通常使用递归方法解决。然而，我们也可以使用迭代方法，借助栈来模拟递归过程，实现二叉树路径总和问题的解法。本文将详细介绍使用迭代方法解决二叉树路径总和问题的思路和实现。

算法思路

1. 初始化栈： 首先，我们初始化一个栈，用于模拟递归过程。栈中的每个元素是一个结构体，包含当前节点、路径和以及剩余的路径总和。
2. 迭代遍历二叉树： 我们使用迭代方法遍历二叉树，每次遍历一个节点时，将当前节点、路径和以及剩余的路径总和入栈。同时，我们将剩余的路径总和减去当前节点的值，表示路径和的剩余部分。
3. 处理叶子节点： 当遍历到叶子节点时，判断剩余的路径总和是否等于叶子节点的值。如果相等，将该路径加入结果集。
4. 继续遍历： 如果当前节点不是叶子节点，将其右子节点（如果存在）和左子节点（如果存在）以及相应的路径和入栈，继续遍历。
5. 返回结果集： 最终，栈中存储的所有路径即为满足路径总和等于指定值的所有路径。

代码实现

以下是C语言中使用迭代方法解决二叉树路径总和问题的代码实现：

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

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct StackNode {
    struct TreeNode* node;
    int sum;
};

struct Stack {
    struct StackNode* data;
    int top;
    int capacity;
};

struct Stack* initStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->data = (struct StackNode*)malloc(sizeof(struct StackNode) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

void push(struct Stack* stack, struct TreeNode* node, int sum) {
    stack->top++;
    stack->data[stack->top].node = node;
    stack->data[stack->top].sum = sum;
}

struct StackNode pop(struct Stack* stack) {
    struct StackNode node = stack->data[stack->top];
    stack->top--;
    return node;
}

bool isLeaf(struct TreeNode* node) {
    return (node != NULL && node->left == NULL && node->right == NULL);
}

int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    struct Stack* stack = initStack(1000);
    int** result = (int**)malloc(sizeof(int*) * 1000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1000);
    int resultSize = 0;

    push(stack, root, targetSum - root->val);
    struct TreeNode* prev = NULL;

    while (stack->top != -1) {
        struct StackNode current = pop(stack);
        struct TreeNode* node = current.node;
        int sum = current.sum;

        if (prev != NULL) {
            prev->val = -prev->val;
        }

        sum -= node->val;

        if (isLeaf(node) && sum == 0) {
            int* path = (int*)malloc(sizeof(int) * 1000);
            int pathSize = 0;
            int pathSum = 0;
            struct TreeNode* temp = node;
            while (temp != NULL) {
                path[pathSize] = temp->val;
                pathSize++;
                pathSum += temp->val;
                temp->val = -temp->val;
                if (temp->left != NULL && temp->left->val > 0) {
                    temp = temp->left;
                } else if (temp->right != NULL && temp->right->val > 0) {
                    temp = temp->right;
                } else {
                    temp = NULL;
                }
            }
            for (int i = 0; i < pathSize / 2; i++) {
                int temp = path[i];
                path[i] = path[pathSize - 1 - i];
                path[pathSize - 1 - i] = temp;
            }
            result[resultSize] = path;
            (*returnColumnSizes)[resultSize] = pathSize;
            resultSize++;
        }

        if (node->right != NULL && node->right->val > 0) {
            push(stack, node->right, sum - node->right->val);
        }

        if (node->left != NULL && node->left->val > 0) {
            push(stack, node->left, sum - node->left->val);
        }

        prev = node;
    }

    *returnSize = resultSize;
    return result;
}

int main() {
    // 构造一棵二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 5;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 4;
    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->val = 11;
    root->left->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->left->val = 7;
    root->left->left->left->left = NULL;
    root->left->left->left->right = NULL;
    root->left->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->right->val = 2;
    root->left->left->right->left = NULL;
    root->left->left->right->right = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 8;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 13;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 4;
    root->right->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->left->val = 5;
    root->right->right->left->left = NULL;
    root->right->right->left->right = NULL;
    root->right->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->right->val = 1;
    root->right->right->right->left = NULL;
    root->right->right->right->right = NULL;

    int returnSize;
    int* returnColumnSizes;
    int** result = pathSum(root, 22, &returnSize, &returnColumnSizes);

    // 打印结果
    printf("存在路径总和等于22的路径：\n");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) {
                printf(", ");
            }
        }
        printf("]\n");
    }

    // 释放内存
    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);

    return 0;
}

算法分析

• 时间复杂度： 该算法的时间复杂度主要取决于二叉树的节点数，因为我们需要遍历所有的节点。在最坏情况下，时间复杂度为O(n)，其中n是二叉树的节点数。
• 空间复杂度： 使用了一个栈来存储节点，栈的空间复杂度为O(n)。此外，存储结果集的空间复杂度也为O(n)。因此，总的空间复杂度为O(n)。

示例和测试

我们使用上述算法对一颗二叉树进行路径总和为22的测试，输出结果如下：

存在路径总和等于22的路径：
[5, 4, 11, 2]
[5, 8, 4, 5]

总结

本文详细介绍了使用迭代方法解决二叉树路径总和问题的算法思路和实现。通过使用栈模拟递归过程，我们可以在不使用递归的情况下解决这个问题。该方法具有较好的通用性，适用于不同形态的二叉树。在实际应用中，这种迭代方法为解决类似问题提供了一种新的思路和方法。