leetcood学习笔记-111-二叉树的最小深度

题目描述：

第一次提交：

class Solution(object):

    def minDepth(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        if not root:

            return 0

        if root.left and root.right:

            return min(self.minDepth(root.left)+1,self.minDepth(root.right)+1)

        if not root.left and root.right:

            return self.minDepth(root.right)+1

        if not root.right and root.left:

            return self.minDepth(root.left)+1

        if not root.left and not root.right:

            return 1

优化后：

class Solution(object):

    def minDepth(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        if not root: return 0

        if not root.left or not root.right:

            return 1 + max(self.minDepth(root.right), self.minDepth(root.left))

        else:

            return 1 + min(self.minDepth(root.right), self.minDepth(root.left))

方法二：广度优先 O(N)

from collections import deque

class Solution:

    def minDepth(self, root):

        if not root:

            return 0

        else:

            node_deque = deque([(1, root),])

        while node_deque:

            depth, root = node_deque.popleft()

            children = [root.left, root.right]

            if not any(children):

                return depth

            for c in children:

                if c:

                    node_deque.append((depth + 1, c))

巴特西

leetcood学习笔记-111-二叉树的最小深度

最新文章

热门文章