111. 二叉树的最小深度 [easy]

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

通过次数84,739 | 提交次数198,450

Second Try

2020-06-26

平时自己写的版本，虽然简洁，速度也没有快到前面去。

看了一下题解，对题解的深度递归又没法一眼看明白，果然看题解理解别人的思路比做题麻烦多了。

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not (root and root.val is not None):
            return 0
        queue = [(1, root)]
        while len(queue):
            level, node = queue.pop(0)
            if not (node.left or node.right):
                return level
            if node.left:
                queue.append((level + 1, node.left))
            if node.right:
                queue.append((level + 1, node.right))

First Try

2020-06-26

一开始对叶子节点的理解有误，导致又贡献了一次错误提交。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not (root and root.val is not None):
            return 0

        l = 1
        queue = [root, None]
        while len(queue):
            node = queue.pop(0)
            if node is None:
                if len(queue):  # 这个判断总是被忘掉
                    l += 1
                    queue.append(None)
                continue
            # 叶子节点的概念是没有left node也没有right node, 而不是仅没有其中之一
            if (not node.left) and (not node.right):
                break
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return l

执行用时：52 ms, 在所有 Python 提交中击败了10.66%的用户
内存消耗：15.4 MB, 在所有 Python 提交中击败了16.67%的用户

111. 二叉树的最小深度 [easy]​

Second Try​

First Try​

111. 二叉树的最小深度 [easy]

Second Try

First Try