111. 二叉树的最小深度

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

解法一：递归

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:    #递归出口，空节点
            return 0
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

乍一看似乎没问题，然而对于特殊情形，如[1,2]这组数据，输出是1，但是正确为2，因为右子为空，不构成子树，即右子树没有高度。因此需要对递归出口重新考虑，到叶节点（左右子均为空）即是出口。此外左右子树不能用min来求较小值，因为有可能其中一棵子树不存在，不能比较。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:    #排除根为空
            return 0
        if not root.left and not root.right:    #递归出口，叶节点
            return 1
        min_depth = sys.maxsize  #最小深度，初始设为最大整数
        if root.left:
            min_depth = min(min_depth, self.minDepth(root.left))
        if root.right:
            min_depth = min(min_depth, self.minDepth(root.right))    
        return min_depth + 1

解法二：层序

从根开始计算深度，初始=1。遇到叶节点就查看当前深度，并与最小深度记录比较。

import queue
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        min_depth = sys.maxsize  #记录最小深度
        q = queue.Queue()
        q.put(root)
        #层序
        while not q.empty():
            depth += 1
            count = q.qsize()
            for _ in range(count):
                tmp = q.get()
                if tmp.left:
                    q.put(tmp.left)
                if tmp.right:
                    q.put(tmp.right)
                if not tmp.left and not tmp.right:
                    min_depth = min(depth, min_depth)        
        return min_depth