题目

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

引言

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

算法思路

  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),因为它递归地遍历整个树并使用堆栈。在实际应用中,最小深度可以用于确定二叉树的高度,或者检查是否满足某些平衡性条件。

标签: 编程算法, 编程算法题, 编程算法大全, 编程算法流程, 算法设计与分析, 数据结构与算法, 算法优化, 算法实现, 常见编程算法, 编程算法入门, 编程算法进阶, 编程算法精通