1. 打开转盘锁(中等)2. 二叉树的最小深度(简单)
1. 打开转盘锁(中等)地址: https://leetcode-cn.com/problems/open-the-lock/
2022/01/30
做题反思:
class Solution { public int openLock(String[] deadends, String target) { Set2. 二叉树的最小深度(简单)deads = new HashSet<>(); for (String s : deadends) { deads.add(s); } Queue q = new linkedList<>(); Set visited = new HashSet<>(); q.offer("0000"); visited.add("0000"); int step = 0; while (!q.isEmpty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { String cur = q.poll(); if (cur.equals(target)) { return step; } if (deads.contains(cur)) { continue; } for (int j = 0; j < 4; j++) { String up = addOne(cur, j); if (!visited.contains(up)) { q.offer(up); visited.add(up); } String down = minunesOne(cur, j); if (!visited.contains(down)) { q.offer(down); visited.add(down); } } } step++; } return -1; } String addOne(String cur, int j) { char[] ch = cur.toCharArray(); if (ch[j] == '9') { ch[j] = '0'; } else { ch[j]++; } return new String(ch); } String minunesOne(String cur, int j) { char[] ch = cur.toCharArray(); if (ch[j] == '0') { ch[j] = '9'; } else { ch[j]--; } return new String(ch); } }
地址: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
2022/01/28
做题反思:
递归
class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } int minLeft = minDepth(root.left); int minRight = minDepth(root.right); if (minLeft == 0 || minRight == 0) { return Math.max(minLeft, minRight) + 1; } return Math.min(minLeft, minRight) + 1; } }
BFS
class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Queueq = new linkedList<>(); q.offer(root); int depth = 1; while(!q.isEmpty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); if (cur.left == null && cur.right == null) { return depth; } if (cur.left != null) { q.offer(cur.left); } if (cur.right != null) { q.offer(cur.right); } } depth++; } return depth; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)