[Leetcode][python]Minimum Depth of Binary Tree
程序员文章站
2024-02-29 12:00:34
...
题目大意
求二叉树的最小深度
解题思路
联想到求最大深度,递归到最深处往上层慢慢+1。
代码
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
if root.left != None and root.right == None:
return self.minDepth(root.left)+1
if root.left == None and root.right != None:
return self.minDepth(root.right)+1
return min(self.minDepth(root.left),self.minDepth(root.right))+1
总结
这题有意思的是,并不能直接将求最大深度的max改为min就完了,有很多坑在里面。一开始我以为只要将[],[0],[1,2]等情况考虑掉就可以了,其实在只有一边又子节点的情况下,是仍然需要遍历的。
例如:
要分几种情况考虑:
1. 树为空,则为0。
2. 根节点如果只存在左子树或者只存在右子树,则返回值应为左子树或者右子树的(最小深度+1)。
3. 如果根节点的左子树和右子树都存在,则返回值为(左右子树的最小深度的较小值+1)。
推荐阅读
-
leetcode--minimum-depth-of-binary-tree
-
[Leetcode][python]Minimum Depth of Binary Tree
-
111. Minimum Depth of Binary Tree
-
111. Minimum Depth of Binary Tree 二叉树的最小深度
-
LeetCode:102.Binary Tree Level Order Traversal
-
Leetcode 452. Minimum Number of Arrows to Burst Balloons(python+cpp)
-
LeetCode 662 Maximum Width of Binary Tree 二叉树的最大宽度
-
[leetcode]662. Maximum Width of Binary Tree(Python)
-
Leetcode Maximum Depth of Binary Tree
-
leetcode【104】Maximum Depth of Binary Tree