1.广度优先搜索（一）

2020-06-28 本文已影响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 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。

转换后得到的单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回一个空列表。

所有单词具有相同的长度。

所有单词只由小写字母组成。

字典中不存在重复的单词。

你可以假设 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 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。

转换后得到的单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 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. 克隆图中等

给你无向连通图中一个节点的引用，请你返回该图的 [深拷贝]（克隆）。
图中的每个节点都包含它的值 val（int）和其邻居的列（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.广度优先搜索（一）

题目汇总

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

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

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

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

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

126. 单词接龙 II困难（不会）

127. 单词接龙中等（不会）

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

133. 克隆图中等（不会）

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

101. 对称二叉树简单

思路一：递归

思路二：迭代

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

思路：迭代

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

思路：迭代

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

思路：迭代

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

思路：递归

126. 单词接龙 II困难

127. 单词接龙中等

130. 被围绕的区域中等

思路一：递归+DFS

思路二：BFS+非递归

133. 克隆图中等

思路：广度优先搜索

199. 二叉树的右视图中等

思路：BFS

猜你喜欢

热点阅读