09-二叉树最小深度-广度优先

题目链接

广度优先：一层一层遍历，当找到有一个叶子节点是空的时候，就找到了最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 构建包装节点的类
    public class QueueNode {
        TreeNode node;
        int dep;
        QueueNode(TreeNode node,int dep) {
            this.node = node;
            this.dep = dep;
        }
    }
    // 广度优先
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<QueueNode>  queue = new LinkedList<>();
        queue.offer(new QueueNode(root, 1)); // offer加入，poll出队列
        while(!queue.isEmpty()) { // 空的话就无法获取节点
            QueueNode node =  queue.poll();
            TreeNode n1 = node.node;
            if(n1.left == null && n1.right == null) {
                return node.dep;
            }
            if(n1.left != null) {
                queue.offer(new QueueNode(n1.left, node.dep+1));
            }
            if(n1.right != null) {
                queue.offer(new QueueNode(n1.right, node.dep+1));
            }
        }
        return 0;
    }
}