美文网首页
1.广度优先搜索(一)

1.广度优先搜索(一)

作者: 今天柚稚了么 | 来源:发表于2020-06-28 11:37 被阅读0次

    https://leetcode-cn.com/tag/breadth-first-search/

    题目汇总

    101. 对称二叉树简单[✔]

    102. 二叉树的层序遍历中等[✔]

    103. 二叉树的锯齿形层次遍历中等

    107. 二叉树的层次遍历 II简单

    111. 二叉树的最小深度简单[✔]

    126. 单词接龙 II困难(不会)

    127. 单词接龙中等(不会)

    130. 被围绕的区域中等[✔](递归+DFS更简单)

    133. 克隆图中等(不会)

    199. 二叉树的右视图中等[✔]

    101. 对称二叉树简单

    给定一个二叉树,检查它是否是镜像对称的。
    例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
    但是这个[1,2,2,null,3,null,3] 则不是镜像对称的。


    进阶:你可以运用递归和迭代两种方法解决这个问题吗?
    思路一:递归

    递归过程:
    判断两个指针当前节点值是否相等
    判断 A 的右子树与 B 的左子树是否对称
    判断 A 的左子树与 B 的右子树是否对称

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetrical(root.left,root.right);
            
        }
        private boolean isSymmetrical(TreeNode root1, TreeNode root2){
            if(root1 == null && root2 == null)
                return true;
            if(root1 == null || root2 == null)
                return false;
            
            if(root1.val == root2.val)
                return isSymmetrical(root1.left, root2.right) && isSymmetrical(root1.right, root2.left);
            return false;
        }
    }
    
    思路二:迭代

    用队列来实现,代码来自题解https://leetcode-cn.com/problems/symmetric-tree/solution/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/

    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了34.23%的用户
        public boolean isSymmetric(TreeNode root) {
            if(root==null || (root.left==null && root.right==null)) {
                return true;
            }
            //用队列保存节点
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            //将根节点的左右孩子放到队列中
            queue.add(root.left);
            queue.add(root.right);
            while(queue.size()>0) {
                //从队列中取出两个节点,再比较这两个节点
                TreeNode left = queue.removeFirst();
                TreeNode right = queue.removeFirst();
                //如果两个节点都为空就继续循环,两者有一个为空就返回false
                if(left==null && right==null) {
                    continue;
                }
                if(left==null || right==null) {
                    return false;
                }
                if(left.val!=right.val) {
                    return false;
                }
                //将左节点的左孩子, 右节点的右孩子放入队列
                queue.add(left.left);
                queue.add(right.right);
                //将左节点的右孩子,右节点的左孩子放入队列
                queue.add(left.right);
                queue.add(right.left);
            }
            
            return true;
            
        }
    }
    

    102. 二叉树的层序遍历中等

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
    示例:
    二叉树:[3,9,20,null,null,15,7],


    返回其层次遍历结果:
    [
    [3],
    [9,20],
    [15,7]
    ]
    思路:迭代

    广度优先需要用队列作为辅助结构,我们先将根节点放到队列中,然后不断遍历队列。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了18.52%的用户
        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 n = queue.size();//获取当前队列的长度,也就是当前这一层的节点个数
                List<Integer> level = new ArrayList<>();
                for(int i=0;i<n;i++){
                    TreeNode node = queue.poll();
                    level.add(node.val);//将队列中的元素都取出来(也就是获取这一层的节点)
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
                res.add(level);
               
            }
        return res;
        }
    }
    

    103. 二叉树的锯齿形层次遍历中等

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
    例如:
    给定二叉树 [3,9,20,null,null,15,7],


    返回锯齿形层次遍历如下:
    思路:迭代
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了97.68%的用户
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
                queue.add(root);//将根节点放入队列中,然后不断遍历队列
            }
            int count = 0;
            while(!queue.isEmpty()){
                int n = queue.size();//获取当前队列的长度,也就是当前这一层的节点个数
                List<Integer> level = new ArrayList<>();
                for(int i=0;i<n;i++){
                    TreeNode node = queue.poll();
                    level.add(node.val);//将队列中的元素都取出来(也就是获取这一层的节点)
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
                if(count % 2 == 1)//奇数层反转
                    Collections.reverse(level);//reverse() 用于反转指定列表中元素的顺序。
                count++;
                //res.add(new ArrayList<>(level));
                res.add(level);
               
            }
        return res;
    
        }
    }
    

    107. 二叉树的层次遍历 II简单

    给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
    例如:给定二叉树 [3,9,20,null,null,15,7],


    返回其自底向上的层次遍历为:
    思路:迭代
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了98.82%的用户
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            LinkedList<List<Integer>> res = new LinkedList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
                queue.add(root);//将根节点放入队列中,然后不断遍历队列
            }
            
            while(!queue.isEmpty()){
                int n = queue.size();//获取当前队列的长度,也就是当前这一层的节点个数
                List<Integer> level = new ArrayList<>();
                for(int i=0;i<n;i++){
                    TreeNode node = queue.poll();
                    level.add(node.val);//将队列中的元素都取出来(也就是获取这一层的节点)
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
                res.addFirst(level);//此方法将元素加入到列表最前面的位置
            }
        return res;
        }
    }
    

    111. 二叉树的最小深度简单

    给定一个二叉树,找出其最小深度。
    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    说明: 叶子节点是指没有子节点的节点。
    示例:
    给定二叉树 [3,9,20,null,null,15,7],返回它的最小深度 2.

    思路:递归
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int minDepth(TreeNode root) {
            if(root == null)
                return 0;
            if(root.left == null && root.right == null)
                return 1;
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            if(root.left == null || root.right == null){
                return leftDepth + rightDepth + 1;//这个判断容易落下
            }
                
        return Math.min(leftDepth,rightDepth) + 1;
    
        }
    }
    

    126. 单词接龙 II困难

    给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:

    1. 每次转换只能改变一个字母。
    2. 转换后得到的单词必须是字典中的单词。

    说明:

    • 如果不存在这样的转换序列,返回一个空列表。
    • 所有单词具有相同的长度。
    • 所有单词只由小写字母组成。
    • 字典中不存在重复的单词。
    • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
      示例 1:
      输入:
      beginWord = "hit",
      endWord = "cog",
      wordList = ["hot","dot","dog","lot","log","cog"]
      输出:
      [
      ["hit","hot","dot","dog","cog"],
      ["hit","hot","lot","log","cog"]
      ]
      示例 2:
      输入:
      beginWord = "hit"
      endWord = "cog"
      wordList = ["hot","dot","dog","lot","log"]
      输出: []
      解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。

    127. 单词接龙中等

    给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:

    1. 每次转换只能改变一个字母。
    2. 转换后得到的单词必须是字典中的单词。

    说明:

    • 如果不存在这样的转换序列,返回 0。
    • 所有单词具有相同的长度。
    • 所有单词只由小写字母组成。
    • 字典中不存在重复的单词。
    • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

    示例 1:
    输入:
    beginWord = "hit",
    endWord = "cog",
    wordList = ["hot","dot","dog","lot","log","cog"]
    输出: 5
    解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    返回它的长度 5。
    示例 2:
    输入:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]
    输出: 0
    解释: endWord "cog" 不在字典中,所以无法进行转换。

    130. 被围绕的区域中等

    给定一个二维的矩阵,包含 'X''O'字母 O)。
    找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。
    示例:
    X X X X
    X O O X
    X X O X
    X O X X
    运行你的函数后,矩阵变为:
    X X X X
    X X X X
    X X X X
    X O X X
    解释:
    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

    思路一:递归+DFS

    主要是寻找和边界联通的 'O',把这种情况下的 'O' 换成 '#' 作为占位符,待搜索结束之后,遇到 'O' 替换为 'X' (和边界不连通的 'O');遇到 '#' ,替换回 'O'(和边界连通的 'O')。

    //2020.06.17
    class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了98.17%的用户
        public void solve(char[][] board) {
            if (board == null || board.length == 0) 
                return;
            int row = board.length;
            int col = board[0].length;
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    boolean isEdge = (i == 0 || j == 0 || i == row-1 || j == col-1);
                    if(isEdge && board[i][j]=='O'){//处理边界上的O
                        dfs(board, i, j);
                    }
                }
            }
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';//搜索结束之后,和边界不连通的'O'替换为'X
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';//搜索结束之后,和边界连通的'O'(即为'#')替换回'O'
                    }
                }
            }
    
    
        }
        //和边界连通的'O'改为'#'
        public void dfs(char[][] board, int i ,int j){
            if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || 
                  board[i][j] == '#' || board[i][j] == 'X'){
                return;
            }
            board[i][j] = '#';
            dfs(board, i - 1, j); // 上
            dfs(board, i + 1, j); // 下
            dfs(board, i, j - 1); // 左
            dfs(board, i, j + 1); // 右
        }
    }
    
    思路二:BFS+非递归

    代码来自https://leetcode-cn.com/problems/surrounded-regions/solution/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/

    class Solution {//执行用时 :4 ms, 在所有 Java 提交中击败了29.78%的用户
         public class Pos{//内部类 Pos 来标记横坐标和纵坐标
            int i;
            int j;
            Pos(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
    
        public void solve(char[][] board) {
            if(board == null || board.length == 0)
                return;
            int row = board.length;
            int col = board[0].length;
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    boolean isEdge = (i == 0 || j == 0 || i == row - 1 || j == col - 1);
                    if(isEdge && board[i][j] == 'O'){//处理边界上的O
                        bfs(board, i, j);
                    }
                }
            }
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    if(board[i][j] == 'O'){
                        board[i][j] = 'X';//搜索结束之后,和边界不连通的'O'替换为'X
                    }
                    if(board[i][j] == '#'){
                        board[i][j] = 'O';//搜索结束之后,和边界连通的'O'(即为'#')替换回'O'
                    }
                   
                }
            }
    
        }
        //和边界连通的'O'改为'#'
        public void bfs(char[][] board, int i, int j) {
            Queue<Pos> queue = new LinkedList<>();//用队列来记录状态
            queue.add(new Pos(i, j));
            board[i][j] = '#';
            while (!queue.isEmpty()) {
                Pos current = queue.poll();
                // 上
                if (current.i - 1 >= 0 
                    && board[current.i - 1][current.j] == 'O') {
                    queue.add(new Pos(current.i - 1, current.j));
                    board[current.i - 1][current.j] = '#';
                    // 没有continue.
                }
                // 下
                if (current.i + 1 <= board.length - 1 
                    && board[current.i + 1][current.j] == 'O') {
                    queue.add(new Pos(current.i + 1, current.j));
                    board[current.i + 1][current.j] = '#';      
                }
                // 左
                if (current.j - 1 >= 0 
                    && board[current.i][current.j - 1] == 'O') {
                    queue.add(new Pos(current.i, current.j - 1));
                    board[current.i][current.j - 1] = '#';
                }
                // 右
                if (current.j + 1 <= board[0].length - 1 
                    && board[current.i][current.j + 1] == 'O') {
                    queue.add(new Pos(current.i, current.j + 1));
                    board[current.i][current.j + 1] = '#';
                }
            }
        }
    }
    

    133. 克隆图中等

    给你无向 连通图中一个节点的引用,请你返回该图的 [深拷贝](克隆)。
    图中的每个节点都包含它的值 valint) 和其邻居的列(list[Node])。
    class Node {
    public int val;
    public List<Node> neighbors;
    }
    测试用例格式:
    简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。
    邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
    给定节点将始终是图中的第一个节点(值为 1)。你必须将 **给定节点的拷贝 **作为对克隆图的引用返回。

    思路:广度优先搜索

    代码来自题解https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode/

    class Solution {//执行用时 :38 ms, 在所有 Java 提交中击败了38.20%的用户
        public Node cloneGraph(Node node) {
            if (node == null) return null;
            Map<Node, Node> visited = new HashMap<>();
    
            Node clone = new Node(node.val, new ArrayList<>());
            visited.put(node, clone);
    
            Deque<Node> queue = new LinkedList<>();
            queue.offer(node);
            while (!queue.isEmpty()) {
                Node tmp = queue.poll();//从队列首部取出一个节点
                for (Node n : tmp.neighbors) {//遍历该节点的所有邻接点
                    if (!visited.containsKey(n)) {//如果某个邻接点还没被访问,则该邻接点一定在 visited 中,那么从 visited 获得该邻接点。
                        visited.put(n, new Node(n.val, new ArrayList<>()));//创建一个新的节点存储在 visited 中。
                        queue.offer(n);//将新遇到的节点添加到队列中
                    }
                    visited.get(tmp).neighbors.add(visited.get(n));//将克隆的邻接点添加到克隆图对应节点的邻接表中
                }
            }
            return clone;
        }
    }
    

    199. 二叉树的右视图中等

    给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
    示例:

    思路:BFS

    这道题就是在 102. 二叉树的层序遍历的基础上扩展的,使用层序遍历,并只保留每层最后一个节点的值

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    //2020.06.17
    class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了94.94%的用户
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
                queue.add(root);//将根节点放入队列中,然后不断遍历队列
            }
            
            while(!queue.isEmpty()){
                int n = queue.size();//获取当前队列的长度,也就是当前这一层的节点个数
                //遍历当前层的所有节点
                for(int i=0;i<n;i++){
                    TreeNode node = queue.poll();
                   //将当前节点的左右孩子入队
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                    if(i == n - 1){
                        res.add(node.val);//将当前层的最后一个节点放入结果列表
                    }
                }
            }
        return res;
    
        }
    }
    

    相关文章

      网友评论

          本文标题:1.广度优先搜索(一)

          本文链接:https://www.haomeiwen.com/subject/jcglxktx.html