Easy

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明： 叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

  • 树中节点数的范围在 [0, 10^5] 内
  • -1000 <= Node.val <= 1000

解题思路

解题思路

这道题要求找到二叉树的最小深度，即从根节点到最近叶子节点的路径长度。有两种主要的解法：

方法一：深度优先搜索（DFS）

使用递归的方式遍历二叉树。需要注意的是，最小深度必须到达叶子节点，所以需要特别处理只有一个子节点的情况：

  • 如果当前节点为空，返回 0
  • 如果当前节点是叶子节点，返回 1
  • 如果只有左子树或只有右子树，返回存在的那个子树的最小深度 + 1
  • 如果左右子树都存在，返回两个子树最小深度的较小值 + 1

方法二：广度优先搜索（BFS）（推荐）

使用层序遍历的方式，从根节点开始逐层访问。一旦遇到第一个叶子节点，就找到了最小深度，这样可以避免访问更深的节点，在某些情况下更高效。

BFS 方法特别适合这道题，因为它能保证第一次遇到的叶子节点就是距离根节点最近的，可以提前终止搜索。

代码实现

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        
        queue<TreeNode*> q;
        q.push(root);
        int depth = 1;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 找到叶子节点，返回当前深度
                if (!node->left && !node->right) {
                    return depth;
                }
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth++;
        }
        
        return depth;
    }
};

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        from collections import deque
        queue = deque([(root, 1)])
        
        while queue:
            node, depth = queue.popleft()
            
            # 找到叶子节点，返回当前深度
            if not node.left and not node.right:
                return depth
            
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))
        
        return 0

public class Solution {
    public int MinDepth(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int depth = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                
                // 找到叶子节点，返回当前深度
                if (node.left == null && node.right == null) {
                    return depth;
                }
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            depth++;
        }
        
        return depth;
    }
}

var minDepth = function(root) {
    if (!root) return 0;
    
    const queue = [root];
    let depth = 1;
    
    while (queue.length > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            
            // 找到叶子节点，返回当前深度
            if (!node.left && !node.right) {
                return depth;
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        depth++;
    }
    
    return depth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
BFS（推荐）O(N)O(W)
DFSO(N)O(H)

说明：

  • N 为二叉树的节点数
  • W 为二叉树的最大宽度
  • H 为二叉树的高度
  • BFS 在最坏情况下需要存储一层的所有节点，DFS 的空间复杂度取决于递归栈的深度

相关题目