代码随想录算法训练营第十四天|Day14二叉树

思路

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

// 动态数组结构体以存储路径
typedef struct {
    char** paths;   // 存储路径的指针数组
    int size;       // 当前路径数量
    int capacity;   // 当前路径数组的容量
} PathList;

// 创建路径列表
PathList* createPathList(int capacity) {
    PathList* list = (PathList*)malloc(sizeof(PathList));
    list->paths = (char**)malloc(capacity * sizeof(char*));
    list->size = 0;
    list->capacity = capacity;
    return list;
}

// 追加路径到路径列表
void addPath(PathList* list, const char* path) {
    if (list->size == list->capacity) {
        list->capacity *= 2;  // 扩展容量
        list->paths = (char**)realloc(list->paths, list->capacity * sizeof(char*));
    }
    list->paths[list->size] = strdup(path);  // 复制字符串
    list->size++;
}

// 递归查找路径
void findPaths(struct TreeNode* root, char* path, PathList* list) {
    if (root == NULL) return;

    // 保存当前节点的值
    char buffer[20];  // 存储当前节点的值的字符串
    snprintf(buffer, sizeof(buffer), "%d", root->val);

    // 如果当前路径为空，则直接添加当前节点的值
    if (strlen(path) == 0) {
        strcat(path, buffer);
    } else {
        strcat(path, "->");
        strcat(path, buffer); // 正确拼接
    }

    // 检查是否是叶子节点
    if (root->left == NULL && root->right == NULL) {
        addPath(list, path);  // 记录完整路径
    } else {
        // 递归遍历左子树和右子树
        findPaths(root->left, path, list);
        findPaths(root->right, path, list);
    }

    // 回溯，移除当前节点的值以便在其他路径中使用
    // 注意：在这里不需要查找最后一个箭头而是直接去掉当前节点的字符串
    size_t len = strlen(path);
    if (len > 0) {
        size_t pathLen = strlen(buffer);
        if (len >= pathLen + 2) { // len - 2是为了考虑去掉箭头和当前节点
            path[len - (pathLen + 2)] = '\0'; // 保留路径的前一部分
        } else {
            path[0] = '\0'; // 确保字符串为空
        }
    }
}

// 主函数，用于返回所有从根到叶子的路径
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    PathList* list = createPathList(10);  // 初始化路径列表
    char path[200] = ""; // 用于存储当前路径

    findPaths(root, path, list); // 查找所有路径

    *returnSize = list->size; // 返回路径数量
    return list->paths; // 返回路径数组
}

// 释放路径列表和每个路径字符串的内存
void freePathList(PathList* list) {
    for (int i = 0; i < list->size; i++) {
        free(list->paths[i]); // 释放每个路径字符串
    }
    free(list->paths); // 释放路径数组
    free(list); // 释放路径列表结构
}

// 释放树节点的内存
void freeTree(struct TreeNode* root) {
    if (root) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 创建新节点
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;
}

学习反思

我自己写出来的有问题，改了好久，c语言好烦。

int sumOfLeftLeaves(struct TreeNode* root){
    if(!root)
        return 0;
    int leftValue = sumOfLeftLeaves(root->left);
    int rightValue = sumOfLeftLeaves(root->right);
    int midValue = 0;
    if(root->left && (!root->left->left && !root->left->right))
        midValue = root->left->val;  
    return leftValue + rightValue + midValue;
}

int countNodes(struct TreeNode* root) {
    if(!root)
        return 0;
    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);
    return leftCount + rightCount + 1;
}
int countNodes(struct TreeNode* root){
    return getNodes(root);
}

int countNodes(struct TreeNode* root){
    int totalNum = 0;
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100);
    int stackTop = 0;
    if(root)
        stack[stackTop++] = root;
    while(stackTop) {
        struct TreeNode* tempNode = stack[--stackTop];
        totalNum++;
        if(tempNode->left)
            stack[stackTop++] = tempNode->left;
        if(tempNode->right)
            stack[stackTop++] = tempNode->right;
    }
    return totalNum;
}