欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[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]等情况考虑掉就可以了,其实在只有一边又子节点的情况下,是仍然需要遍历的。
例如:
[Leetcode][python]Minimum Depth of Binary Tree

要分几种情况考虑:
1. 树为空,则为0。
2. 根节点如果只存在左子树或者只存在右子树,则返回值应为左子树或者右子树的(最小深度+1)。
3. 如果根节点的左子树和右子树都存在,则返回值为(左右子树的最小深度的较小值+1)。

相关标签: python leetcode