聊聊算法——BFS和DFS

如果面试字节跳动和腾讯,上来就是先撕算法,阿里就是会突然给你电话,而且不太在意是周末还是深夜,

别问我怎么知道的,想确认的可以亲自去试试。说到算法,直接力扣hard三百题也是可以的,但似乎会比较伤脑,

有没一些深入浅出系列呢,看了些经典的算法,发现其实很多算法是有框架的,今天就先说下很具代表的树

算法BFS和DFS,再来点秒杀题。

作者原创文章,谢绝一切转载,违者必究。

准备:

Idea2019.03/JDK11.0.4

难度: 新手--战士--老兵--大师

目标:

  1. 理解BFS和DFS框架
  2. 框架应用扩展

1 介绍

BFS和DFS,即“广度优先”和“深度优先”,如下图二叉树前序BFS为 1-2-3-4-5 ,DFS为 1-2-4-5-3,本文中算法均以此树为例:

聊聊算法——BFS和DFS

2 算法理解

2.1 DFS递归模式

如下,这寥寥几行,即完成了二叉树先序、中序和后序遍历算法,这就是算法框架

public static void dfs(Node root){
if (root == null){
return;
}
// 先序遍历位置
dfs(root.left);
// 中序遍历位置
dfs(root.right);
// 后序遍历位置
}
其他更复杂的场景可以依此来类推,比如多路树的遍历,是不是很简单:
private static class Node {
public int value;
public Node[] children;
}
public static void dfs(Node root){
if (root == null){
return;
}
// 对node做点事情
for (Node child:children
) {
dfs(child);
}
}
 

我们来具体化一下,用Java实现,似乎一点也不难,通过调整打印root.value的位置,即可实现前中后序遍历二叉树了:

public class DFS {
private static class Node {
public int value;
public Node left;
public Node right; public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
public Node(int value) {
this.value = value;
}
public Node() {
}
} /** DFS的递归实现,代码简单,但如果层次过深可能会导致栈溢出 */
public static void dfs(Node root){
if (root == null){
return;
}
// 先序遍历位置
System.out.println(root.value);
dfs(root.left);
// 中序遍历位置
dfs(root.right);
// 后序遍历位置
}
public static void main(String[] args) {
Node root = new Node(1,new Node(),new Node(3));
root.left = new Node(2,new Node(4),new Node(5));
// 递归DFS测试
dfs(root);
}
}
 

2.2 DFS非递归模式

为了将DFS理解的更透彻一点,再说栈方式实现,事实上,前面的递归本质上也是栈实现,只是代码上没表现出来,这是第二个框架:

/** 非递归,栈方式进行DFS*/
public static void dfs2(Node root){
if (root == null){
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while( !stack.isEmpty()){
Node treeNode = stack.pop();
// System.out.println(treeNode.value);
if (treeNode.right != null){
stack.push(treeNode.right);
}
if (treeNode.left != null){
stack.push(treeNode.left);
}
}
}
以上代码解析:先初始化一个栈,然后将根root压栈,循环中,先弹栈,如果弹出元素的子节点非空,则将子节点压栈,

因读出是先左后右,故这里压栈要先右后左, 看下动图实现,更好理解:

聊聊算法——BFS和DFS

2.3 BFS队列模式

对比一下,BFS使用队列实现,而 DFS使用栈实现,这是第三个框架:

public class BFS {

    private static class Node{
public int value;
public Node left;
public Node right; public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
public Node(int value) {
this.value = value;
}
public Node() {
}
} /** 非递归,广度优先算法是使用队列*/
private static void bfs(Node root) {
if(root == null){
return;
}
// LinkedList implements Queue
Queue<Node> queue = new LinkedList<>();
queue.add(root); while ( !queue.isEmpty()){
Node node = queue.poll();
// System.out.println(node.value);
if (node.left != null){
queue.add(node.left);
}
if (node.right != null){
queue.add(node.right);
}
}
} public static void main(String[] args) {
Node root = new Node(1,new Node(),new Node(4));
root.left = new Node(2,new Node(5),new Node(6));
bfs(root);
}
}
以上代码解析:LinkedList 实现了Queue接口,故可以直接作为队列使用;循环体中,子节点入队列是先左后右,

动画展示:

聊聊算法——BFS和DFS

3 算法扩展应用

3.1 BST二叉搜索树

这里举例为节点大于左子节点,且小于右子节点的BST。

查找一个数是否存在,其实就是DFS的变形:

static boolean searchBST(Node root,int target){
if (root == null) return false;
if (root.value == target){
return true;
}
if(root.value < target){
return searchBST(root.right,target);
}
if (root.value > target){
return searchBST(root.left,target);
}
return false;
}
插入一个数:
static Node insertBST(Node root,int target){
if (root == null) return new Node(target);
// BST中一般不会插入已有的元素
if(root.value < target){
root.right = insertBST(root.right,target);
}
if (root.value > target){
root.left = insertBST(root.left,target);
}
return root;
}
以上代码解析:如果根为空,则直接生成只有一个根节点的BST,如果根不为空,则看要插入的目标值应该在左边还是右边。

若在右边,且右子树为空,则先生成一个 new Node,然后赋值给右指针,理解 root.right = insertBST(root.right,target);

等价于两行Node node = new Node(target); root.right = node; 这样,即实现了插入;若应该在右边且右子树非空,

则递归下去,直到子节点有为空的节点。

删除一个数:

static Node deleteBST(Node root,int target){
if (root == null) return null;
if (root.value == target){
if(root.left == null)
return root.right;
if (root.right == null)
return root.left;
Node node = getMin(root.right);
root.right = deleteBST(root.right,node.value);
}else if(root.value < target){
root.right = deleteBST(root.right,target);
}else if (root.value > target){
root.left = deleteBST(root.left,target);
}
return root;
}
// 以找到最小值节点为例:根要小于右子树,直接循环到叶子
private static Node getMin(Node node) {
while (node.left != null)
node = node.left;
return node;
}
以上代码解析:1.我们先回归到最简单模型,根为空,直接返回;删除只带有左子节点的根,则左子节点上升为根;删除只带有右子节点的根,

则右子节点上升为根;删除带有左右子节点的根,则右子节点上升为根(或者左子节点上升为根) 2. 删除带有左右子树的根,则是找到右子树最

小节点(或者左子树最大节点),再做递归 3.这个算法不算最优解,更好的解决方案是先将要删除的根和右子树最小值(或者左子树最大值)做交换,

再删除目标值节点,这样就可以避免树结构的过多调整。

3.2 其他树

秒杀,题一,找出的最小/最大深度:

static int minDepth(Node root){
if (root == null) return 0;
int leftDepth = minDepth(root.left) + 1;
int rightDepth = minDepth(root.right) + 1;
return Math.min(leftDepth,rightDepth);
} static int maxDepth(Node root){
if (root == null) return 0;
int leftDepth = maxDepth(root.left) + 1;
int rightDepth = maxDepth(root.right) + 1;
return Math.max(leftDepth,rightDepth);
}
 

题二,二叉树,返回其按层序遍历得到的结果,即将每相同深度的节点放一个List,再将各层数组放入另一个List返回:

// 最终结果存放
private static List<List<Integer>> result = new ArrayList<>(); /** BFS 按层输出二叉树,每一层为一个数组放进一个ArrayList */
private static List<List<Integer>> bfs(Node root) {
if(root == null){
return null;
}
// LinkedList implements Queue
Queue<Node> queue = new LinkedList<>();
queue.add(root); while ( !queue.isEmpty()){
List<Integer> levelNodes = new ArrayList<>();
// 同一层的节点数量
int levelNum = queue.size();
for (int i = 0; i < levelNum; i++) {
Node node = queue.poll();
levelNodes.add(node.value);
System.out.println(node.value);
if (node.left != null){
queue.add(node.left);
}
if (node.right != null){
queue.add(node.right);
}
}
result.add(levelNodes);
}
return result;
}
以上代码解析:一看就很明显是BFS算法框架,只是需要额外记录每层的节点个数,每次while循环将处理相同层节点;每次for循环,

将同层的节点放入层记录List,并同时将其子节点加入队列;最终返回结果List。

那么使用DFS是否也可以呢,下面给出了一个算法,这个算法很妙,推荐收藏:

// 最终结果存放
private static List<List<Integer>> result = new ArrayList<>();
private static List<List<Integer>> dfs(Node root,int level) {
if (root == null) return;
if (result.size() < level + 1){
result.add(new ArrayList<>());
}
List<Integer> levelList = result.get(level);
levelList.add(root.value);
// 理解算法的辅助输出
System.out.println(result);
// 遍历左右子树
dfs(root.left,level +1);
dfs(root.right,level +1);
return result;
}
// 运行测试
System.out.println(dfs(root,0));
以上代码解析:DFS递归中附加一个层数变量,于是每递归一层,则层数变量会加 1 ,而根的层数变量可以初始化为0,

这样在递归的过程中顺带通过result大小判断是否需要添加一个空数组,随后将节点加入与层变量对应的数组中,理解算法的辅助输出如下:

聊聊算法——BFS和DFS

总结:这里说了三套算法框架,请问看官掌握了吗?

全文完!


我的其他文章:

只写原创,敬请关注

上一篇:PAT Advanced 1076 Forwards on Weibo (30) [图的遍历,BFS,DFS]


下一篇:图的遍历算法:DFS、BFS