二叉树的最小深度

问题描述

来源：LeetCode第111题

难度：简单

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。

BFS解决

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。如上图所示，我们可以使用 BFS 一层一层的遍历，在第一次遇到叶子节点的时候，直接返回这个叶子节点的层数即可。

代码语言：javascript代码运行次数：0运行复制
public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int level = 0;
    while (!queue.isEmpty()) {
        level++;// 每往下一层就加 1
        // 当前层的节点个数
        int size = queue.size();
        while (size-- > 0) {
            TreeNode cur = queue.poll();//出队
            // 如果当前节点 cur 是叶子节点，直接返回level即可
            if (cur.left == null && cur.right == null)
                return level;
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
    }
    return -1;
}

DFS解决

在来看下 DFS 解决思路，这个和二叉树的最大深度类似，首先递归计算左右子树的结果，最后在合并，看下代码。

代码语言：javascript代码运行次数：0运行复制
public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    // 递归计算左右子树的结果
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    // 这里合并
}

这里的关键点是怎么合并，计算二叉树最大深度的时候《二叉树的最大深度》，最后我们取的是两个子节点的最大值，那么计算二叉树最小深度的时候是不是取两个节点的最小深度呢，明显不是的。比如上面图 (2) 中，节点 1 没有左子节点，所以节点 1 的左子树计算的结果为 0 ，右子树计算的结果为 2 ，如果取最小值在加 1 结果就是 1 ，但很明显这棵树的最小深度不是 1 。

解这题之前我们首先要明白什么是最小深度，就是从根节点到最近叶子节点的最短路径上的节点数量，这里要注意的到叶子节点，所以如果有两个子节点的时候我们取他们两个的最小值，但如果只有一个子节点的时候，我们取不为空的那个子节点计算的结果，如果两个子节点都为空，直接取 0 就行了 ，来看下代码：

代码语言：javascript代码运行次数：0运行复制
public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    // 两个子树至少有一个为空的情况
    if (left == 0 || right == 0)
        return left + right + 1;
    // 两个子树都不为空
    return Math.min(left, right) + 1;
}

大家可以关注我的视频号，每晚直播刷题。

本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。原始发表：2023-10-23，如有侵权请联系 cloudcommunity@tencent 删除二叉树introot遍历视频