[算法]广度优先搜索BFS
BFS(广度优先搜索 Breadth-First Search)[1]
BFS基本介绍
是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
BFS实现方法
- 首先将根节点放入队列中。
- 从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜索并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。 - 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
- 重复步骤2。
BFS的一些应用
- 查找图中所有连接组件（Connected Component）。一个连接组件是图中的最大相连子图。
- 查找连接组件中的所有节点。
- 查找非加权图中任两点的最短路径。
- 测试一图是否为二分图。
算法题
判断二叉树是否对称[2]
在以下例子中我们会将二叉树的同一深度节点遍历完全后再遍历子节点。
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的
1
/ \
2 2
/ \ /\
3 4 4 3
下面这棵二叉树不对称。
1
/ \
2 2
\ \
3 3
如 输入{1,2,2} 输出true
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isSymmetric (TreeNode root) {
if (root == null) {
return true;
}
TreeNode left = root.left;
TreeNode right = root.right;
return check(left, right);
}
//通过迭代遍历树
public boolean check (TreeNode left, TreeNode right) {
// 边界条件返回
if (left == null && right == null) {
return true;
}
// 不符合要求返回
if (left == null && right != null || left != null && right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
//迭代左节点的左子节点与右节点的右子节点
if (check(left.left, right.right) == false) {
return false;
}
//迭代左节点的右子节点与右节点的左子节点
if (check(left.right, right.left) == false) {
return false;
}
return true;
}
}