LeetCode0111.二叉树的最小深度【Easy】【Python】【二叉树】问题LeetCode给定一棵二叉树，求它的最小深度.Theminimum深度是从根节点向下到最近的叶子节点的最短路径上的节点数。注意：叶子是没有子节点的节点。示例：给定二叉树[3,9,20,null,null,15,7],3/\920/\157returnitsminimumdepth=2.问题给定一棵二叉树，找出它的最小深度。最小深度是从根节点到最近的叶节点的最短路径上的节点数。解释：叶节点是指没有子节点的节点。例子：给定一棵二叉树[3,9,20,null,null,15,7]，3/\920/\157返回它的最小深度2。思路解决方案1：分别对每个非叶子节点进行DFS计算其左右子树的最小叶节点深度。时间复杂度：O(n)，其中n是二叉树中的节点数。空间复杂度：O(h)，其中h是二叉树的高度。Python3代码#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defminDepth(self,root:TreeNode)->int:#解决方案一：DFS#rootisemptyifnotroot:return0#bothleftandrightsubtreesareemptyifnotroot.leftandnotroot.right:return1min_depth=10**9ifroot.left:min_depth=min(self.minDepth(root.left),min_depth)ifroot.right:min_depth=min(self.minDepth(root.right),min_depth)returnmin_depth+1方案二：当BFS找到叶节点时,直接返回这个叶子节点的深度。时间复杂度：O(n)，其中n是二叉树中的节点数。空间复杂度：O(h)，其中h是二叉树的高度。Python3代码#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defminDepth(self,root:TreeNode)->int:#方案二：BFSimportcollections#根为空ifnotroot:return0que=collections.deque([(root,1)])whileque:node,depth=que.popleft()#到达叶子节点ifnotnode.leftandnotnode.right:returndepthifnode.left:que.append((node.left,depth+1))ifnode.right:que.append((node.right,depth+1))返回0GitHub链接Python
