力扣(LeetCode)之二叉树最小深度（深度优先、广度优先）

题目：

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

示例：

输入：root = [3,9,20,null,null,15,7]
输出：2

方法一：深度优先算法

深度优先算法就是利用递归找到二叉树的最后一层，然后每次都是先左右后，比较左右节点的大小就能够获取最小深度。

# 深度优先搜索算法
def fun1(root):
    if root == None: return 0
    if root.left == None and root.right == None: return 1

    mins = float("inf")
    if root.left != None:
        mins = min(fun1(root.left), mins)
    if root.right != None:
        mins = min(fun1(root.right), mins)
    print(root.val, mins)
    return mins+1

方法二：广度优先算法

广度优先算法与深度优先算法不同，深度优先算法首先就需要找到二叉树的叶子节点向前遍历。而广度优先算法是对二叉树一层一层进行遍历，如果发现某一层出现了叶子节点就说明该二叉树的最小深度就是层数。那么怎么实现这样的一层一层进行遍历呢？就可以使用到队列这个数据结构，先进先出。其具体代码如下：

# 广度优先搜索
def fun2(root):
    if root == None: return 0 
    q = queue.Queue()
    root.deep = 1
    q.put(root)
    while not q.empty():
        node = q.get() 
        if node.left == None and node.right == None:
            return node.deep 
        if node.left != None:
            node.left.deep = node.deep + 1
            q.put(node.left)
        if node.right != None:
            node.right.deep = node.deep + 1
            q.put(node.right)
    return 0

总体代码:

import queue
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.deep = 0

# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)

# 二叉树2
node6 = TreeNode(6)
node5 = TreeNode(5,None,node6)
node4 = TreeNode(4,None,node5)
node3 = TreeNode(3,None, node4)
node2 = TreeNode(2,None,node3)

root = node2

# 深度优先搜索算法
def fun1(root):
    if root == None: return 0
    if root.left == None and root.right == None: return 1

    mins = float("inf")
    if root.left != None:
        mins = min(fun1(root.left), mins)
    if root.right != None:
        mins = min(fun1(root.right), mins)
    return mins+1

# 广度优先搜索
def fun2(root):
    if root == None: return 0 
    q = queue.Queue()
    root.deep = 1
    q.put(root)
    while not q.empty():
        node = q.get() 
        if node.left == None and node.right == None:
            return node.deep 
        if node.left != None:
            node.left.deep = node.deep + 1
            q.put(node.left)
        if node.right != None:
            node.right.deep = node.deep + 1
            q.put(node.right)
    return 0

        
print(fun2(root))