C语言算法-解答二叉树的最小深度算法问题的C语言实现

题目

给定一棵二叉树，求其最小深度。最小深度是从根节点到最近的叶子节点的最短路径的节点数。

引言

最小深度是二叉树的一个重要性质，它表示从根节点到最近的叶子节点的最短路径。求解最小深度通常涉及遍历二叉树，找到最短路径的长度。

算法思路

1. 递归遍历： 我们可以使用递归的方法遍历二叉树，计算左子树和右子树的最小深度。
2. 基本情况： 如果当前节点为空，返回0。如果当前节点是叶子节点（即没有左子树和右子树），返回1。
3. 递归计算： 递归计算左子树和右子树的最小深度，然后取较小值，并加1，即为当前节点的最小深度。
4. 返回结果： 返回根节点的最小深度。

代码实现

以下是C语言中求二叉树的最小深度的代码实现：

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

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

int minDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);
    if (root->left == NULL) {
        return rightDepth + 1;
    }
    if (root->right == NULL) {
        return leftDepth + 1;
    }
    return (leftDepth < rightDepth ? leftDepth : rightDepth) + 1;
}

算法分析

• 时间复杂度： 递归遍历整个二叉树，每个节点只被访问一次，所以时间复杂度是O(n)，其中n是二叉树的节点数。
• 空间复杂度： 递归调用的堆栈深度最多为树的高度，最坏情况下为O(n)。

示例和测试

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->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    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 = NULL;

    int result = minDepth(root);
    printf("最小深度：%d\n", result);

    return 0;
}

这段代码将构造一棵二叉树，然后使用minDepth函数来求解其最小深度。

总结

通过递归遍历二叉树，我们可以求解二叉树的最小深度。这个算法的时间复杂度为O(n)，空间复杂度为O(n)，因为它递归地遍历整个树并使用堆栈。在实际应用中，最小深度可以用于确定二叉树的高度，或者检查是否满足某些平衡性条件。