力扣搜索
- BFS 广度优先搜索
- 101. 对称二叉树
- 1.要求
- 2.思路
- 279 完全平方数
- 1 要求
- 2 思路
- DFS 深度优先搜索
- backtracking 回溯
BFS 广度优先搜索 广度优先搜索：广度优先搜索一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。
在程序实现 BFS 时需要考虑以下问题：
队列：用来存储每一轮遍历得到的节点；
标记：对于遍历过的节点，应该将它标记，防止重复遍历。
101. 对称二叉树 1.要求
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
22
/ \ / \
34 43
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
22
\\
33
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分
2.思路
1.递归查找对比是否对称；
2.利用BFS 遍历比较队列中左右两边的元素是否对称；
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root,root);
}
public static boolean isMirror(TreeNode left,TreeNode right){if(left==null&& right==null) return true;
if(left==null || right==null) return false;
return (left.val==right.val) && isMirror(left.left,right.right)&& isMirror(left.right,right.left);
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue q = new LinkedList<>();
q.add(root);
q.add(root);
while(!q.isEmpty()){
TreeNode t1=q.poll();
TreeNode t2=q.poll();
if(t1==null && t2==null) continue;
if(t1==null || t2==null) return false;
if(t1.val!=t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
}
279 完全平方数 1 要求
【力扣搜索】给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
2 思路
将问题转化成图论
该算法在往队列里面添加节点的时候会 add 很多重复的节点，导致超时，
优化办法是，加入 visited 数组，检查要 add 的数据是否已经出现过了，防止数据重复出现，从而影响图的遍历;
class Solution {
public int numSquares(int n) {
Listsquares=genrateSqute(n);
Queue queue = new LinkedList<>();
boolean[] visted = new boolean[n + 1];
queue.add(n);
visted[n]=true;
int level=0;
while(!queue.isEmpty()){
int size=queue.size();
level++;
while(size-->0){
int cur=queue.poll();
for(int s : squares){
int next=cur-s;
if(next<0){
break;
}
if(next==0){
return level;
}
if(visted[next]){
continue;
}
visted[next]=true;
queue.add(next);
}
}}return 1;
}
public staticList genrateSqute(int n){
List squares=new ArrayList<>();
int square=1;
int i=1;
while(i<=n){
squares.add(square);
square=(i+1)*(i+1);
i++;
}
return squares;
}
} DFS 深度优先搜索 待续…
backtracking 回溯 待续…
链接：https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md
https://leetcode-cn.com/problems/symmetric-tree
