聊聊算法——BFS和DFS

2023-01-28 21:51:21

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

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

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

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

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

准备：

Idea2019.03/JDK11.0.4

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

目标：

理解BFS和DFS框架
框架应用扩展

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

总结：这里说了三套算法框架，请问看官掌握了吗？

全文完！

我的其他文章：

只写原创，敬请关注

码农公寓