C++实现LeetCode 111：二叉树最小深度算法解析

沈亦白

发布时间：2026-10-16| 2人浏览过

原创

二叉树的最小深度定义为从根节点到最近叶子节点的最短路径上的节点数量。本文将介绍使用C++解决的两种主要方法：基于DFS的递归法和基于BFS的层序遍历法，重点解析在处理单边子树时的边界条件。

问题定义与核心逻辑

题目要求找出二叉树的最小深度，即从根节点向下到达最近叶子节点（Leaf Node）的最短路径上的节点总数。一个叶节点被定义为一个没有子节点的节点。

解题的关键在于区分“空节点”和“叶子节点”。当节点只有左子树或右子树时，不能简单地对非空子树加1，而必须继续深入查找；仅当左右子树均为空时，才代表找到了叶子节点。这一逻辑是本题区别于“最大深度”题目的核心考点。

解法一：深度优先搜索 (DFS)

利用递归思想，我们可以自顶向下地检查每个节点。对于当前节点，需要分情况讨论：

基本情况：如果当前节点为空，返回深度0。
单边子树：如果左子节点为空，说明最小深度一定在右子树中，递归计算右子树并加1；反之亦然。
双边子树：如果左右子节点都存在，则取左右子树深度的较小值，再加1。

第1步：编写递归函数入口

首先判断根节点是否为空，若为空直接返回0。

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 1. 基本情况：节点为空
        if (!root) return 0;
        
        // 2. 左子树为空，最小深度在右子树
        if (!root->left) return 1 + minDepth(root->right);
        
        // 3. 右子树为空，最小深度在左子树
        if (!root->right) return 1 + minDepth(root->left); 
        
        // 4. 左右子树都存在，取较小者
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

这种写法简洁明了，但在极端不平衡的二叉树（如退化为链表）情况下，递归深度较大，可能影响性能。

解法二：广度优先搜索 (BFS)

使用队列进行层序遍历。因为我们要找的是最小深度，所以一旦在某一层遇到第一个叶子节点，即可立即返回当前的层数，无需继续遍历整个树，这在一定程度上比DFS更高效。

第2步：初始化队列与层数计数器

将根节点入队，初始化结果变量 res 为0，用于记录当前所在的层数。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        // 初始化队列，放入根节点
        queue<TreeNode*> q{{root}};
        
        while (!q.empty()) {
            ++res; // 开始新的一层
            int n = q.size();
            
            // 遍历当前层的所有节点
            for (int i = 0; i < n; ++i) {
                auto t = q.front(); 
                q.pop();
                
                // 判断是否为叶子节点
                if (!t->left && !t->right) return res;
                
                // 将非空子节点加入下一层队列
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return -1; // 理论上不会执行到这里
    }
};

BFS的优势在于找到目标后即停止，适合寻找“最近”或“最短”的问题。需要注意的是，在遍历时必须一次性取完当前层的节点数量 n，以确保层数统计准确。