聊聊算法——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,本文中算法均以此树为例:

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压栈,循环中,先弹栈,如果弹出元素的子节点非空,则将子节点压栈,

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

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接口,故可以直接作为队列使用;循环体中,子节点入队列是先左后右,

动画展示:

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大小判断是否需要添加一个空数组,随后将节点加入与层变量对应的数组中,理解算法的辅助输出如下:

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

全文完!

我的其他文章:

 

只写原创,敬请关注

 

© 版权声明
THE END
喜欢就支持一下吧!
点赞0
分享