首页 > 其他分享 >leetcode 二叉树的最小深度

leetcode 二叉树的最小深度

时间:2023-09-17 12:11:06浏览次数:46  
标签:right TreeNode 最小 depth 二叉树 null root leetcode left

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

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

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

示例 1:
image

输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:

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

解题思路

  1. 如果当前节点为null, 返回0
  2. 判断左节点的最小路径,和右节点的最小路径,然后取最小值,即为当前节点的最小深度
  3. 递归思想,从下到上,依次累加最小路径值,得到的值即为最小路径
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if (root == null) {
            return depth;
        }
        depth += 1;
        if (root.left == null && root.right == null) {
            return depth;
        }
        if (root.left == null) {
            return depth + minDepth(root.right);
        } 
        if (root.right == null) {
            return depth + minDepth(root.left);
        }

        int leftDepth = depth + minDepth(root.left);
        int rightDepth = depth + minDepth(root.right);
        return leftDepth > rightDepth ? rightDepth : leftDepth;
    }
}

标签:right,TreeNode,最小,depth,二叉树,null,root,leetcode,left
From: https://www.cnblogs.com/gradyblog/p/17708199.html

相关文章

  • leetcode 平衡二叉树
    给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3:输入:root......
  • [LeetCode] 1222. Queens That Can Attack the King
    Ona 0-indexed 8x8 chessboard,therecanbemultipleblackqueensadonewhiteking.Youaregivena2Dintegerarray queens where queens[i]=[xQueeni,yQueeni] representsthepositionofthe ith blackqueenonthechessboard.Youarealsogivena......
  • #yyds干货盘点# LeetCode程序员面试金典:2 的幂
    题目:给你一个整数 n,请你判断该整数是否是2的幂次方。如果是,返回 true ;否则,返回 false 。如果存在一个整数 x 使得 n==2x ,则认为 n 是2的幂次方。 示例1:输入:n=1输出:true解释:20=1示例2:输入:n=16输出:true解释:24=16示例3:输入:n=3输出:false示例4:输入......
  • #yyds干货盘点# LeetCode程序员面试金典:强密码检验器
    1.简述:满足以下条件的密码被认为是强密码:由至少 6 个,至多 20 个字符组成。包含至少 一个小写 字母,至少 一个大写 字母,和至少 一个数字 。不包含连续三个重复字符(比如 "Baaabb0" 是弱密码,但是 "Baaba0" 是强密码)。给你一个字符串 password ,返回 将 password......
  • LeetCode-Java题解 209. Minimum Size Subarray Sum
    题目地址:209.MinimumSizeSubarraySum解题思路:    看到这道题,心里本身是有双指针这个概念的,但是不知道怎么用,脑子里第一反应就是暴力解法,双for一把梭,然后时间就超时了...看了题解才知道滑动窗口这个解法,不禁直呼妙啊!感觉和双指针非常类似,其核心点在于避免了暴力算法的枚......
  • 中序线索化二叉树
    思路:1、线索化二叉树结点定义与二叉树基本相同,只是在原先的基础上添加了int类型的左右线索标志。 2、定义全局变量pre,用来指向当前结点的前驱结点。 3、构造visit()时,如果访问结点的左孩子为空,需要建立前驱线索并将ltag设为1;如果访问结点的前驱结点不为空且其右孩子为空,需要建立......
  • 中序线索化二叉树
    思路:线索化二叉树结点定义与二叉树基本相同,只是在原先的基础上添加了int类型的左右线索标志。定义全局变量pre,用来指向当前结点的前驱结点。构造visit()时,如果访问结点的左孩子为空,需要建立前驱线索并将ltag设为1;如果访问结点的前驱结点不为空且其右孩子为空,需要建立后继线索并......
  • 力扣-使用最小花费爬楼梯
    1.问题数组的每个索引作为一个阶梯,第i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为0或1的元素......
  • 【代码随想录算法训练营第二天】977.有序数组的平方、209.长度最小的子数组 、59.螺旋
    Day2-数组2023.9.15Leetcode977有序数组的平方给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。初解我还是不能想到暴力解法之外的,对某个问题的最优复杂度也没有概念。就算提示我是用指针,我也想不到思路。现在我知......
  • leetcode1466
    分析:它是有n个节点,n-1条边所以两个节点连接的边只有一条,那么要么是可以从这条边的起点开始能够到达0,要么是不能,不会有回路的情况对于数据结构使用哈希表值为vector容器intbfs(vector<vector<int>>&connections){unordered_map<int,vector<int>>m;for(auto&v:co......