1、深度优先搜索算法
深度优先搜索,即DFS,从root节点开始,尽可能深的搜索每一个分支。把一个分支的结果搜索完以后,再去看下一个分支。
应用场景:
- 二叉树搜索
- 图搜索
例子:走迷宫,从起点开始,一直走到终点或者撞墙后(这就是所谓的 “深度” 优先),回到起点重新开始,可以找到如下两条路(红色箭头和黄色箭头)
用深度优先来看前面回溯中提到的子集求法:从起点开始,首先是一个空集。往下有1、2、3三条路可以走
先逮着1开始走,1符号要求,放入结果集,接着往下走,[1,2],也符合要求,放入结果集,接着往下走,[1,2,3],也符合要求,放入结果集,再往下,就到底了。换另一条路走。
2、宽度优先搜索算法
宽度(广度)优先搜索,即BFS,和DFS不同,BFS是一层一层的处理。BFS一般搭配队列使用。
BFS和DFS的对比:
以从上到下、从左到右遍历以下二叉树为例,采用宽度优先,搭配一个队列,先进先出,计数count = 0。从root开始,root入队,count = 1,出队,同时root的左、右节点入队,并维护count。当count = 0时,说明遍历结束。
即node.val出队,node.left和node.right入队。详细:
- root节点1入队,count = 1
- 根据count,从队列中pop元素,得到root节点,把其值val放入结果集,并把其左右孩子加进来。结果集array = [1]
- 此时,队列中存着2、3这两个节点,count = 2
- 继续根据count = 2来pop两次,并加入元素的左右孩子
- pop出元素2,加入其左右节点4、5,count = 3,结果集array = [1,2]
- pop出元素3,加入其左右节点6、7,count = 4,结果集array = [1,2,3]
- pop出元素4,count = 3,array = [1,2,3,4]
- …
- pop出元素7,count = 0,array = [1,2,3,4,5,6,7]
3、leetcode102:二叉树的层序遍历
和上面分析的BFS遍历二叉树不一样,这题要求输出的结果是分层的,考虑一层一层的处理,并把每层的处理完的结果加入最终的结果集。
外层while执行一次,代表处理了二叉树的一层。内层while执行一次,代表处理这层的每个元素(自身出队、左右节点的值入队)
public class P102 {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (null == root) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() > 0) {
// 存每层的结果
List<Integer> list = new ArrayList<>();
// 每处理完一层,队列的长度,即是下一层元素的数量
int count = queue.size();
// 处理每一层的元素,弹出这一层的每个元素,并把每个元素的左右节点加进去
while (count > 0) {
TreeNode node = queue.poll();
list.add(node.val);
count--;
// 弹出的元素的左右孩子节点的值入队
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// 一层处理结束,把结果加到结果集里,注意别直接add上面的list,防止引用传递,用copy值传递
result.add(new ArrayList<>(list));
}
return result;
}
}
这题很明显的有”层“的概念,用BFS很合适,但DFS也能解。
从root开始,一条路往下走,和前面一层层的取不一样了,DFS解时,每层递归有个level,level = 0,即root节点所在的那层,放到结果集result的0号位置,往下9,放到result的1号元素里面
public class P102 {
public List<List<Integer>> levelOrderByDfs(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (null == root) {
return result;
}
dfs(root, result, 0);
return result;
}
/**
* 深度优先
*
* @param node 节点
* @param result 最终的结果集
* @param level 二叉树中当前的层级
*/
public static void dfs(TreeNode node, List<List<Integer>> result, int level) {
// 终止条件
if (node == null) {
return;
}
// 如果当前层级到了2,那结果集里应该初始化出两个元素,每层的结果存一个结果集的元素里
if (level > result.size() - 1) {
result.add(new ArrayList<>());
}
// 层级所在结果集的位置上,加入这个元素
result.get(level).add(node.val);
if (node.left != null) {
dfs(node.left, result, level + 1);
}
if (node.right != null) {
dfs(node.right, result, level + 1);
}
}
}
4、leetcode107:二叉树的层序遍历II
和前面102题不同的是,要求从叶子节点开始一层层的遍历,输出的顺序刚好相反,当然,可以在102的代码的末尾,直接reverse翻转答案,然后return。
说起翻转,也可自己用栈实现,但除了翻转,有更优实现:结果集result用一个链表,依旧从root节点那一层开始,从上往下一层层处理,但每层的结果,加到result的头部,如此,从上到下遍历完每层后,直接不用翻转就是题解。
Java中,List里面底层是链表的,就不能用ArrayList(数组),而是LinkedList:
public class P107 {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// 用链表对应的LinkedList
List<List<Integer>> result = new LinkedList<>();
if (null == root) {
return result;
}
// 队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() > 0) {
int count = queue.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < count; i++) {
TreeNode node = queue.poll();
levelList.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// 注意这里,每次add的下标是0,即链表队首,这样第二层的结果就会排到第一层
result.add(0, levelList);
}
return result;
}
}
以上实现,注意链表的巧妙之处:
这题要不用BFS,而DFS,那最后就得reverse翻转一下结果集了。虽然BFS能解的,DFS也能解,但这种层级的遍历,BFS更好用。
最后,以上用到的TreeNode:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
5、leetcode938:二叉搜索树的范围和
第一反应是,遍历二叉树,判断每个元素在范围就累加。那应该想到BFS,除了BFS,还有别的实现:不管是前序、中序、后序遍历,一个树,最后肯定会被拆解成一个个只有三个节点的小块,即递归。
解法一:普通递归
从root开始,一分为二的看,最终结果 = 左 + 中 + 右,左边有子树的话,继续左 + 中 + 右,纯递归,递归终止的条件为,节点没有子节点了。代码实现:
public class P938 {
public int rangeSumBST(TreeNode root, int low, int high) {
if (null == root) {
return 0;
}
// 左边那一块,新的root就是root.left
int leftSum = rangeSumBST(root.left, low, high);
// 右边那一块,新的root就是root.right
int rightSum = rangeSumBST(root.right, low, high);
int result = leftSum + rightSum;
// 中间节点
if (low <= root.val && root.val <= high) {
result = result + root.val;
}
return result;
}
}
以上面二叉树为例:
- 第一次递归:root=10, left=5,right=15
- 第二次递归:root=上一层的root.left=5,left=3,right=7
- 第三次递归:root=上一层的root.left=3,left=null,right=null
- 第四次递归:root=上一层的root.left=null,终止递归,回退,返回0
解法二:BFS
一层层的来,平铺扫荡,每一个出队的元素,判断是否在范围内,是则累加
这题的BFS,和BFS概念分析时一样,都不用像前两道题一样分层,一层while就行:
public class P938 {
public int rangeSumBSTByBFS(TreeNode root, int low, int high) {
if (null == root) {
return 0;
}
int result = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.val >= low && node.val <= high) {
result = result + node.val;
}
// 左右节点处理
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return result;
}
}