[数据结构与算法]二叉树的最小深度

Dear 丶 2022-12-07 15:30 137阅读 0赞

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

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

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

示例:

给定二叉树 \[3,9,20,null,null,15,7\],

![在这里插入图片描述][2020091620343918.png_pic_center]

/* bfs写法： */
            var minDepth = function (root) { 
                if (!root) { 
                    return 0
                }
                let queue = [[root, 1]]
                while (queue.length) { 
                    const [n, level] = queue.shift() /* ES6解构赋值 */
                    if (!n.left && !n.right) { 
                        /* 当节点没有左右节点了，说明它是叶子节点，返回level值 */
                        return level
                    }
                    if (n.left) queue.push([n.left, level + 1])
                    if (n.right) queue.push([n.right, level + 1])
                }
            }

/* dfs写法: */
    function minDepth(root) { 
        if (root === null) return 0;
        if (!root.left&&!root.right) return 1;//当前节点为叶子节点时
        if (root.left&&!root.right) return 1+minDepth(root.left);//只有一个字节点时 减枝
        if (!root.left&&root.right) return 1+minDepth(root.right);//只有一个字节点时 减枝
        return 1+Math.min(minDepth(root.left),minDepth(root.right)) //存在两个字节点
    }

[2020091620343918.png_pic_center]: /images/20221123/3f0cadfd2dd94182bac863d55936ba3d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题解】34. 二叉树的最小深度

> 这是一道简单题 > > https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 文章目录

蔚落/ 2024年03月16日 13:45/ 0 赞/ 42 阅读

相关 #数据结构求二叉树的最小深度

//求二叉树根结点到叶子结点的最小深度 int minDepth(struct TreeNode\ root)\{ if(root==NULL)\{ return

末蓝、/ 2023年02月17日 03:22/ 0 赞/ 7 阅读

相关数据结构——二叉树的最小深度算法

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。 ![在这里插入图片描述][wate

今天药忘吃喽~/ 2022年12月23日 09:41/ 0 赞/ 153 阅读

相关【数据结构】二叉树：LeetCode题（三）226. 翻转二叉树，104.二叉树的最大深度，111.二叉树的最小深度

[226. 翻转二叉树¹][226.] 翻转一棵二叉树。示例：输入： 4 / \ 2 7 / \ /

分手后的思念是犯贱/ 2022年12月14日 13:42/ 0 赞/ 134 阅读

相关 [数据结构与算法]二叉树的最小深度

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

Dear 丶/ 2022年12月07日 15:30/ 0 赞/ 138 阅读

相关 [数据结构与算法]二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 \[3,9,2

约定不等于承诺〃/ 2022年12月07日 15:29/ 0 赞/ 139 阅读

相关 leetcode算法【111】二叉树的最小深度

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

悠悠/ 2022年11月26日 07:38/ 0 赞/ 149 阅读

相关数据结构与算法--二叉树的深度问题

二叉树的深度题目：输入一颗二叉树的根，求该树的深度。从根节点到叶子节点一次进过的节点形成的一条路径，最长的路径的长度为树的深度。如下图中二叉树的额深度4，

绝地灬酷狼/ 2022年10月10日 01:27/ 0 赞/ 158 阅读

相关算法-求二叉树最小深度

算法-求二叉树最小深度 -------------------- 基本概念：二叉树的最小深度：从根节点出发到达叶子节点的经过的最少的节点数。 ----------

超、凢脫俗/ 2022年06月14日 08:06/ 0 赞/ 205 阅读

相关【数据结构与算法】树（二）：二叉树

二叉树的特点每个结点最多有两颗子树，所以二叉树的度最大就是2. 左子树和右子树是由顺序的，不能够颠倒，即使树中只有一颗子树，也是要区分它是左子树还是右子树的

骑猪看日落/ 2022年05月21日 06:58/ 0 赞/ 290 阅读