二叉树的最小深度

[编程题]二叉树的最小深度

热度指数：3679 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗节点数为N的二叉树，求其最小深度。最小深度是指树的根节点到最近叶子节点的最短路径上节点的数量。

（注：叶子节点是指没有子节点的节点。）

数据范围：

0<=N<=6000

0<=val<=100

你能使用时间复杂度为O(N)，空间复杂度为O(logN)的解法通过本题吗？

例如当输入{1,2,3,4,5}时，对应的二叉树如下图所示：

可以看出离根节点最近的叶子节点是节点值为3的节点，所以对应的输出为2。

示例1

输入

{1,2,3,4,5}

输出

示例2

输入

{1,#,2,#,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python3

liangzhengjie

from os import remove
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def run(self , root: TreeNode) -> int:
        # write code here
        if root is None:
            return 0
        res, meet = self.tranverse(root)
        if not meet:
            return 1
        return res

    def tranverse(self, root):
        if root is None:
            return 0,False

        if root.left is None and root.right is None:
            # print(root.val)
            return 1,True

        
        l_res, l_meet = self.tranverse(root.left)
        r_res, r_meet = self.tranverse(root.right)

        if l_meet and r_meet:
            return min(l_res, r_res) + 1, True
        elif l_meet:
            return l_res + 1, True
        elif r_meet:
            return r_res + 1, True

        return 0,False

编辑于 2024-03-27 23:34:20 回复(0)