二叉树的最小深度

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

热度指数：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，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python 3

来牛客玩玩

class Solution:
    def run(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        ans = 0
        q = []
        q.append(root)
        while len(q) and q[0]:
            ans += 1
            size = len(q)
            for _ in range(size):
                cur = q.pop(0)
                if (not cur.left) and (not cur.right):
                    return ans
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)

发表于 2022-07-26 07:09:29 回复(0)

Python 3

牛客318213606号

# BFS
class Solution:
    def run(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        
        queue=[]
        queue.append(root)
        res=0
        depth=0
        while queue:
            depth+=1
            size=len(queue)
            for i in range(size):
                cur=queue.pop(0)
                if not cur.left and not cur.right:
                    res=depth
                    return res
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

发表于 2022-02-10 10:48:18 回复(0)

Python 3

Joy_9

class Solution:
    def run(self , root: TreeNode) -> int:
        # write code here
        def depth(root):
            if not root:
                return 0
            if root.left and root.right:
                return min(depth(root.left),depth(root.right))+1
            elif root.left and not root.right:
                return depth(root.left)+1
            elif not root.left and root.right:
                return depth(root.right)+1
            else:
                return 1
        return depth(root)

发表于 2022-01-19 12:10:26 回复(0)