##二叉树最小深度
class Solution {
class QueueNode {
TreeNode node;
int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<QueueNode> queue = new LinkedList<QueueNode>();
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}
return 0;
}
}
##2、打开转盘锁
https://leetcode.cn/problems/open-the-lock/
class Solution {
public int openLock(String[] deadends, String target) {
if ("0000".equals(target)) {
return 0;
}
Set<String> dead = new HashSet<String>();
for (String deadend : deadends) {
dead.add(deadend);
}
if (dead.contains("0000")) {
return -1;
}
int step = 0;
Queue<String> queue = new LinkedList<String>();
queue.offer("0000");
Set<String> seen = new HashSet<String>();
seen.add("0000");
while (!queue.isEmpty()) {
++step;
int size = queue.size();
for (int i = 0; i < size; ++i) {
String status = queue.poll();
for (String : get(status)) {
if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
if (nextStatus.equals(target)) {
return step;
}
queue.offer(nextStatus);
seen.add(nextStatus);
}
}
}
}
return -1;
}
public char numPrev(char x) {
return x == '0' ? '9' : (char) (x - 1);
}
public char numSucc(char x) {
return x == '9' ? '0' : (char) (x + 1);
}
// 枚举 status 通过一次旋转得到的数字
public List<String> get(String status) {
List<String> ret = new ArrayList<String>();
char[] array = status.toCharArray();
for (int i = 0; i < 4; ++i) {
char num = array[i];
array[i] = numPrev(num);
ret.add(new String(array));
array[i] = numSucc(num);
ret.add(new String(array));
array[i] = num;
}
return ret;
}
}
