使用广度优先解决“二叉树的最小深度”问题

二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

解法二：广度优先
1、从上往下，找到一个节点时，标记这个节点的深度。查看该节点是否为叶子节点，如果是直接返回深度（找到第一个叶子节点即可，后面就不需要判断了）。
2、如果不是叶子节点，将其子节点标记深度(在父节点深度的基础上加1)，再判断该节点是否为叶子节点。
3、使用链表实现一个先进先出的队列
4、循环终止条件：队列Queue为空
步骤：
1、二叉树TreeNode新增一个字段deep，用于记录节点的深度。
2、使用链表实现一个先进先出的队列 Queue<TreeNode> queue = new LinkedList<>();
3、记录根节点的深度为1，并将根节点加入队列。
4、当队列不为空时循环，取出队列中元素。
1）如果元素left和right都为null，则循环结束，返回当前node.deep;
2）如果元素有left，将left的深度+1，node.left.deep = node.deep + 1;
3）如果元素有right，同理。
时间复杂度：O(N)
空间复杂度：O(N)

package od1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的最小深度（广度优先）
 * 给定一个二叉树，找出其最小深度，求最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 原文地址：https://www.codernav.com/2845.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest32 {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        // 广度优先
        System.out.println(f(node1));
    }

    public static int f(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 使用链表实现一个先进先出的队列
        Queue<TreeNode> queue = new LinkedList<>();
        // TreeNode无法记录深度，需要新增字段deep
        root.deep = 1;
        // 向队列添加元素，offer()与add()区别是前者当队列满了时不会抛异常，而是返回false
        queue.offer(root);
        // 队列为空跳出循环
        while (!queue.isEmpty()) {
            // 从队列中取出元素
            TreeNode node = queue.poll();
            // 左右节点都为空，则为叶子结点，循环结束
            if (node.left == null && node.right == null) {
                return node.deep;
            }
            // 不为空，则加入队列
            if (node.left != null) {
                node.left.deep = node.deep + 1;
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.deep = node.deep + 1;
                queue.offer(node.right);
            }

        }

        return 0;

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // 深度（广度优先维护深度）
    int deep;

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

两种算法的区别：深度优先与广度优先的区别是深度优先把叶子节点的深度标记为1，广度优先把根节点的深度标记为1。深度优先从下往上遍历，广度优先从上往下遍历。