leetcode代码记录(二叉树的最小深度

简介: leetcode代码记录(二叉树的最小深度

1. 题目:

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

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

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

示例 1:

输入:root = [3,9,20,null,null,15,7]

输出:2

示例 2:

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

输出:5

2. 我的代码:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 后序遍历
        # 递归
        def minDep(node):
            # 终止条件
            if node == None:
                return 0
            left_minDep = minDep(node.left)
            right_minDep = minDep(node.right)
            if left_minDep == 0 or right_minDep == 0:
                return 1 + left_minDep + right_minDep
            else:
                return 1 + min(left_minDep, right_minDep)

        return minDep(root)

这个题继续使用求解高度的后序遍历求解,比较方便。

首先确定终止条件:叶子节点时返回;然后确定后序遍历的逻辑,但是,存在的一个bug是,最小深度的定义为从叶子节点到根节点的最小路径。所以,应当排除掉有一边是None的节点,不然都会被这一侧同化成0。统一返回1 + left_minDep + right_minDep即可。

对于叶子节点或者两侧都非空的节点,返回1 + min(left_minDep, right_minDep)即可。

目录
相关文章
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
18 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
21 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2