题1：

111. 二叉树的最小深度

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

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

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

 

示例 1：

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

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

 

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     class Node{
18         TreeNode treenode;
19         int depth;
20         Node(TreeNode treenode,int depth){
21             this.treenode=treenode;
22             this.depth=depth;
23         }
24     }
25     public int minDepth(TreeNode root) {
26         Queue<Node> queue=new LinkedList<>();
27         if (root==null) return 0;
28         queue.offer(new Node(root,1));
29         while (!queue.isEmpty()){
30             Node temp=queue.poll();
31             TreeNode tree=temp.treenode;
32             if (tree.left==null&&tree.right==null) return temp.depth;
33             if (tree.left!=null) queue.offer(new Node(tree.left,temp.depth+1));
34             if (tree.right!=null) queue.offer(new Node(tree.right,temp.depth+1));
35         }
36         return 0;
37     }
38 }

思路：BFS搜索，找到没有叶子的节点就返回深度。定义了一个节点类，记录当前节点的深度。因为一直向下搜索，所以不会发生重复的现象。

题2：

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

 

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

 

提示：

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target 不在 deadends 之中
• target 和 deadends[i] 仅由若干位数字组成

 1 class Solution {
 2     public int openLock(String[] deadends, String target) {
 3         Queue<String> queue=new LinkedList<>();
 4         queue.offer("0000");
 5         int count=0;
 6         Map<String,Integer> map=new HashMap<>();
 7         for (String s:deadends){
 8             map.put(s,map.getOrDefault(s,0)+1);
 9         }
10         if (map.containsKey("0000")) return -1;
11         map.put("0000",1);
12         while (!queue.isEmpty()){
13             int len=queue.size();
14             for (int l=0;l<len;l++){
15                 String s=queue.poll();
16                 if (s.equals(target)) return count;
17             for (int i=0;i<4;i++){
18                 String x=generateadd(s,i);
19                 if (map.containsKey(x)) continue;
20                 else {
21                     queue.offer(x);
22                     map.put(x,map.getOrDefault(x,0)+1);
23                 }
24             }
25             for (int i=0;i<4;i++){
26                 String x=generate(s,i);
27                 if (map.containsKey(x)) continue;
28                 else {
29                     queue.offer(x);
30                     map.put(x,map.getOrDefault(x,0)+1);
31                 }
32             }
33             }
34             
35             count++;
36         }
37         return -1;
38     }
39 
40     public String generateadd(String s,int k){
41         StringBuffer sb=new StringBuffer();
42         for (int i=0;i<s.length();i++){
43             char c=s.charAt(i);
44             if (i!=k) sb.append(c);
45             else {
46                 sb.append(((int)c-'0'+1)%10);
47             }
48         }
49         return sb.toString();
50     }
51 
52     public String generate(String s,int k){
53         StringBuffer sb=new StringBuffer();
54         for (int i=0;i<s.length();i++){
55             char c=s.charAt(i);
56             if (i!=k) sb.append(c);
57             else {
58                 sb.append(((int)c-'0'+9)%10);
59             }
60         }
61         return sb.toString();
62     }
63 }

思路：BFS，map可以用set优化。