[Leetcode][python]Minimum Depth of Binary Tree

Myth丶恋晨 2022-06-11 08:16 239阅读 0赞

题目大意

求二叉树的最小深度

解题思路

联想到求最大深度，递归到最深处往上层慢慢+1。

代码

  1. class Solution(object):
  2.     def minDepth(self, root):
  3.         """
  4.         :type root: TreeNode
  5.         :rtype: int
  6.         """
  7.         if root == None:
  8.             return 0
  9.         if root.left != None and root.right == None:
  10.             return self.minDepth(root.left)+1
  11.         if root.left == None and root.right != None:
  12.             return self.minDepth(root.right)+1
  13.         return min(self.minDepth(root.left),self.minDepth(root.right))+1

总结

这题有意思的是，并不能直接将求最大深度的max改为min就完了，有很多坑在里面。一开始我以为只要将[],[0],[1,2]等情况考虑掉就可以了，其实在只有一边又子节点的情况下，是仍然需要遍历的。
例如：
这里写图片描述

要分几种情况考虑：

  1. 树为空，则为0。
  2. 根节点如果只存在左子树或者只存在右子树，则返回值应为左子树或者右子树的（最小深度+1）。
  3. 如果根节点的左子树和右子树都存在，则返回值为（左右子树的最小深度的较小值+1）。

发表评论

表情：
评论列表 （有 0 条评论，239人围观）

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

相关阅读