LeetCode广度、深度优先搜索

广度优先搜索

广度优先搜索（也称宽度优先搜索，缩写BFS即即Breadth First Search）是连通图的一种遍历算法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。其属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。

所采用的策略可概况为越早被访问到的顶点，其邻居顶点越早被访问。于是，从根顶点s的BFS搜索，将首先访问顶点s；再依次访问s所有尚未访问到的邻居；再按后者被访问的先后次序，逐个访问它们的邻居。一般用队列queue数据结构来辅助实现BFS算法。

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

class Solution {
    /**
     * 思路：用队列存储每一层的数字，然后用变量记录当前层级元素的个数
     * 创建当前层级集合，遍历当前层级的size，弹出当列当前数添加到集合，判断当前节点左右节点是否为空，不为空加入到当前队列中
     * 注：每一层取当前层是从队列取前面数，存下一层是放入队列尾部，所以不会有冲突
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }

        while(!queue.isEmpty()) {
            //如果当前队列不为空，将当前队列的当前层弹出队列，存储数组中
            int size = queue.size();
            List<Integer> curLevel = new ArrayList<>();
            for (int i=0;i<size;i++) {
                //当前层级可以继续弹出
                TreeNode node = queue.poll();
                curLevel.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(curLevel);
        }
        return res;
    }
}

深度优先搜索

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用栈stack数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

题解：

class Solution {
     /**
     * 节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else { //获取左子树的最大深度和右子树最大深度对比，选取大的，再+1，为当前节点的最大深度
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}
``

#### [二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

#####题解：

class Solution {
public int minDepth(TreeNode root) {
//思路：得到树的最底层的叶子节点，即左右节点都为null，设置深度为1，从下往上找
//当前节点深度为取左右节点的深度较小值，+1，即当前节点最小深度作为函数返回值，该函数为递归调用函数
if(root == null) {
return 0;
}

    if(root.left == null && root.right == null) {
        return 1;
    }

    int mindepth = Integer.MAX_VALUE;
    if(root.left != null) {
        //左子节点不为空，得到左子节点的深度
        mindepth = Math.min(minDepth(root.left), mindepth);
    }
    if(root.right != null) {
        //右子节点不为空，得到右子节点的深度
        mindepth = Math.min(minDepth(root.right), mindepth);
    }
    return mindepth+1;
}

}