leetcode大厂面试经典算法题-111. 二叉树的最小深度

#头条创作挑战赛#

这题是大厂面试算法题中常见的一道题目，也是DFS深度优先算法中比较典型的一道算法题。谈到DFS，肯定就要扯到BFS了，这里我们也顺带说一下BFS和DFS的区别。BFS常用于找单一的最短路线，比较典型的就是“搜索最优解”，这里其实回溯算法就是BFS；DFS它主要用于找到所有的解的类型的问题，而不是找最优解，并且会记录下素有的解。从上面的描述本质上来看：BFS找到的路径一定是最短的，但是代价就是空间复杂度要比DFS高，原因是在寻找最短路径的时候，会一层一层的向外辐射，随着辐射的层数越来越深，需要记录的节点也越来越多。用二叉树来举例子，空间复杂度是O(2^(n-1))的，但是DFS的空间复杂度是O(lgn)，随着n增大，BFS的空间复杂度也达到一个惊人的地步。

下面我们来写一下DFS的算法的一个基本框架：

// 计算从起点到目标target的最小距离
    int bfs(TreeNode start, TreeNode target) {
        // DFS的核心数据结构，用来存储当前节点所有周围节点
        Queue<TreeNode> q;
        // 集合用来存储已经访问过的节点，避免重复访问，提供执行效率
        Set<TreeNode> set;

        q.add(start);
        set.add(start);
        // 记录步数
        int step = 0;

        while(!q.isEmpty()) {
            // 这里需要记录当前的队列的大小，因为后面会不断从队列中删除数据
            int size = q.size();

            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();

                // 这里判断当前节点是否是目标节点
                if (cur is target) {
                    // 如果是的话，直接返回，DFS的本质是搜索最短路径的
                    return step;
                }

                // 如果不是的话，要将当前节点的周围的节点加入队列
                for(TreeNode node :cur.child()) {
                    //要判断节点是否已经访问过了，访问过的就不要再加入了，相当于一个剪枝的优化手段
                    if (node is not in set) {
                        q.add(node);
                        set.add(node);
                    }
                }
            }
            // 这里是重点，步数的增加是在这里
            step++;
        }
    }           

整体的DFS的算法的框架思想如上所列举的，这个是参看labuladong的算法小抄写的，他整理的特别的好。大多数的dfs算法求最短路径相关的问题，都可以直接套用这个框架。下面就按照这个框架来写一下二叉树的最小深度的解法。

public int minDepth(TreeNode root) {
        // 特殊情况，直接返回
        if (root == null)
            return 0;
        // 核心数据结构，将一个节点周围的所有的节点加入到这个队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // set的作用是避免走回头路，但是二叉树的特性是只能向下走，不会有回头路，这里就不需要使用了
        //Set<TreeNode> set = new HashSet<TreeNode>();

        queue.add(root);
        //set.add(root);
        int step = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 从队列取出当前节点
                TreeNode cur = queue.poll();

                // 判断当前节点是否满足需求，最小深度，其实就是看谁最先到达叶子节点
                if (cur.left == null && cur.right == null) {
                    return step;
                }

                if (cur.left != null) {
                    queue.add(cur.left);
                }

                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            step++;

        }

        return step;
    }           

到这里本文就结束了，算法的道路任重而道远，需要长久的学习。大家在阅读本文的时候要带着对算法的自己的思考，沉淀属于自己的知识。

请点赞关注一下哈，后续就行相关知识分享。