Minimum Depth of Binary Tree

LeetCode 111 二叉树最小深度：BFS 见到第一个叶子即返回；DFS 注意空子树处理。

#algorithm #snippet #evergreen #tree #bfs #dfs #leetcode

[!info] related notes 算法面试题型 MOC 二叉树高频题

Minimum Depth of Binary Tree

LeetCode: https://leetcode.cn/problems/minimum-depth-of-binary-tree/

推荐：BFS

深度按根到叶子的路径节点数计。叶子必须左右孩子都为空，缺少某一个孩子不算叶子。BFS 第一次遇到叶子时的层数就是答案；例如根只有一个叶子孩子时，最小深度为 2 而非 1。

import java.util.*;

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int depth = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                if (cur.left == null && cur.right == null) return depth;
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            depth++;
        }
        return depth;
    }
}

DFS 注意点

如果一个子树为空，最小深度不能取 min(left,right) 直接得到 0，需要特殊处理。

Java 示例使用题目提供的 TreeNode。最坏时间 O(n)，队列 O(w)；BFS 可在首个叶子处提前停止，不保证只访问最短路径上的节点。

Minimum Depth of Binary Tree

推荐：BFS

DFS 注意点

Related