二叉树的最小深度

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

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

初次分析

这个二叉树的深度，我们之前已经做过了。比如平衡二叉树，我们也要计算每个子树的深度。我们只需要返回左右子树的深度最小值即可。

public int minDepth(TreeNode root) {
    if(root==null){return 0;}
    return Math.min(minDepth(root.left)+1,minDepth(root.right)+1);
​
}

继续分析

但是提交代码之后，发现执行失败

这个二叉树的左子树为空，只有右子树。所以根节点不是叶子节点，算出来的1不是正确答案，那么答案就是根节点到他右子树叶子节点的深度。

所以我们要单独的处理这种情况，那么这种情况就是判断根节点的左右子树一方为空的情况。

• 左右子树都为空，那么这个节点就是叶子节点，那么到自身的距离就是1。
• 左子树为空，那么深度就是根节点到右子树叶子节点的距离。
• 右子树为空，那么深度就是根节点到左子树叶子节点的距离。

答案

public int minDepth(TreeNode root) {
        if(root==null){return 0;}
        if(root.left==null&&root.right==null){
            return 1;
        }
        if(root.left==null||root.right==null){
            return minDepth(root.left==null?root.right:root.left)+1;
        }
        return Math.min(minDepth(root.left)+1,minDepth(root.right)+1);
​
    }

复杂度

• 时间复杂度: O(n)，其中 n 是二叉树中的节点个数。最坏的情况就是满二叉树，所有节点都会遍历。
• 空间复杂度：O(n)，递归调用占用的栈空间，其中n就是二叉树的高度。

总结

以上的方法是基于深度优先的算法。这个题的坑就是没有左右子树的时候，这个节点才是叶子节点，计算的结果才是根节点到叶子节点的深度。

找到这个条件之后，这个题其实就不难了。二叉树的深度如下图所示。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！