​LeetCode刷题实战111:二叉树的最小深度

程序IT圈

共 1697字,需浏览 4分钟

 ·

2020-11-30 22:34

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 二叉树的最小深度,我们先来看题面:
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

题意


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

样例

解题

https://zhuanlan.zhihu.com/p/47992915

这个题目求其最小深度不同于最大深度那样,这个要考虑该二叉树的左右子树是否存在,有四个方面

1、该二叉树为空,则返回0;

2、该二叉树不为空,且左右子树均存在,则和求最大深度一样,利用递归的方法求出最小深度

3、该二叉树只存在左子树,则返回值为1

4、该二叉树只存在右子树,则返回值为1

第二种情况时,分别求出左子树的最小值和右子树的最小值,再比较左右子树的最小值也会出现三种情况

a、left小于right时,取left+1

b、left大于right时,取right+1

c、left等于right时,并且left小于最大值,返回left+1

public class Solution {
    public int minDepth(TreeNode root) {
    if(root!=null){
        int left=Integer.MAX_VALUE;
        int right=Integer.MAX_VALUE;
        if(root.left!=null){
            left=minDepth(root.left);
        }
        if(root.right!=null){
            right=minDepth(root.right);
        }
        if(left            return left+1;
        }
        else if(left>right){
            return right+1;
        }
        else if(left==right&&left!=Integer.MAX_VALUE){
            return left+1;
        }
        else{
            return 1;
        }
        
    }
     return 0;
    }
}
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:

LeetCode1-100题汇总,希望对你有点帮助!
LeetCode刷题实战101:对称二叉树
LeetCode刷题实战102:二叉树的层序遍历
LeetCode刷题实战103:二叉树的锯齿形层次遍历
LeetCode刷题实战104:二叉树的最大深度
LeetCode刷题实战105:从前序与中序遍历序列构造二叉树
LeetCode刷题实战106:从中序与后序遍历序列构造二叉树
LeetCode刷题实战107:二叉树的层次遍历 II
LeetCode刷题实战108:将有序数组转换为二叉搜索树

浏览 44
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报