【LeetCode】栈、队列问题：队列与 BFS

比眉伴天荒 2022-10-29 09:12 175阅读 0赞

### 队列 ###

*  只要是树的层序遍历，遍历方法永远都是用 queue，不同题型变得只是添加元素方式（即 addFirst 还是 addLast）

#### [102. 二叉树的层序遍历][102.] ####

难度中等765收藏分享切换为英文接收动态反馈

给你一个二叉树，请你返回其按 **层序遍历** 得到的节点值。 （即逐层地，从左到右访问所有节点）。

**示例：**  
二叉树：`[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回其层序遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

**题解**

*  解法 1： 正常的深度优先遍历，但是状态维护 level，level 相同的加到同层 level 的 list 里面
 *  解法 2：广度优先，用队列

class Solution { 
        public List<List<Integer>> levelOrder(TreeNode root) { 
            List<List<Integer>> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            TreeNode dummy = new TreeNode();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.addLast(root);
            queue.addLast(dummy);
    
            while(queue.size() != 0){ 
                List<Integer> thisLevel = new LinkedList<>();
                TreeNode node;
                while((node = queue.pop()) != dummy){ 
                    thisLevel.add(node.val);
                    if(node.left != null){ 
                        queue.addLast(node.left);
                    }
                    if(node.right != null){ 
                        queue.addLast(node.right);
                    }
                }
                if(queue.size() != 0){ 
                    queue.addLast(dummy);
                }    
                res.add(thisLevel);
            }
    
            return res;
        }
    }

#### [107. 二叉树的层序遍历 II][107. _ II] ####

难度简单400收藏分享切换为英文接收动态反馈

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：  
给定二叉树 `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回其自底向上的层序遍历为：

[
      [15,7],
      [9,20],
      [3]
    ]

**题解**

class Solution { 
        public List<List<Integer>> levelOrderBottom(TreeNode root) { 
            LinkedList<List<Integer>> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            TreeNode dummy = new TreeNode();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.addLast(root);
            queue.addLast(dummy);
    
            while(queue.size() != 0){ 
                TreeNode node;
                List<Integer> level = new LinkedList<>();
                while((node = queue.pop()) != dummy){ 
                    level.add(node.val);
                    if(node.left != null){ 
                        queue.addLast(node.left);
                    }
                    if(node.right != null){ 
                        queue.addLast(node.right);
                    }
                }
    
                if(queue.size() != 0){ 
                    queue.addLast(dummy);
                }
                // 这里，每次放到第一个
                res.addFirst(level);
            }
    
            return res;
        }
    }

#### [103. 二叉树的锯齿形层序遍历][103.] ####

难度中等381收藏分享切换为英文接收动态反馈

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：  
给定二叉树 `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回锯齿形层序遍历如下：

[
      [3],
      [20,9],
      [15,7]
    ]

**题解**

class Solution { 
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) { 
            List<List<Integer>> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            LinkedList<TreeNode> queue = new LinkedList<>();
            TreeNode dummy = new TreeNode();
            queue.addLast(root);
            queue.addLast(dummy);
    
            int level = 1;
    
            while(queue.size() != 0){ 
                TreeNode node;
                LinkedList<Integer> levelData = new LinkedList<>();
                while((node = queue.pop()) != dummy){ 
                    if(level % 2 == 1){ 
                        levelData.addLast(node.val);
                    }else { 
                        levelData.addFirst(node.val);
                    }
    
                    if(node.left != null){ 
                        queue.addLast(node.left);
                    }
                    if(node.right != null){ 
                        queue.addLast(node.right);
                    }
                }
    
                if(queue.size() != 0){ 
                    queue.addLast(dummy);
                }
                level ++;
                res.add(levelData);
            }
    
            return res;
        }
    }

#### [199. 二叉树的右视图][199.] ####

难度中等399收藏分享切换为英文接收动态反馈

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

**示例:**

输入: [1,2,3,null,5,null,4]
    输出: [1, 3, 4]
    解释:
    
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

**题解**

class Solution { 
        public List<Integer> rightSideView(TreeNode root) { 
            List<Integer> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            LinkedList<TreeNode> queue = new LinkedList<>();
            TreeNode dummy = new TreeNode();
            queue.add(root);
            queue.add(dummy);
    
            while(queue.size() != 0){ 
                TreeNode node;
                while((node = queue.pop()) != dummy){ 
                    if(node.left != null){ 
                        queue.addLast(node.left);
                    }
                    if(node.right != null){ 
                        queue.addLast(node.right);
                    }
    
                    if(queue.getFirst() == dummy){ 
                        res.add(node.val);
                    }
                }
    
                if(queue.size() != 0){ 
                    queue.add(dummy);
                }
            }
    
            return res;
        }
    
       
    }

#### [127. 单词接龙][127.] ####

难度困难689收藏分享切换为英文接收动态反馈

字典 `wordList` 中从单词 `beginWord` 和 `endWord` 的 **转换序列** 是一个按下述规格形成的序列：

*  序列中第一个单词是 `beginWord` 。
 *  序列中最后一个单词是 `endWord` 。
 *  每次转换只能改变一个字母。
 *  转换过程中的中间单词必须是字典 `wordList` 中的单词。

给你两个单词 `beginWord` 和 `endWord` 和一个字典 `wordList` ，找到从 `beginWord` 到 `endWord` 的 **最短转换序列** 中的 **单词数目** 。如果不存在这样的转换序列，返回 0。

**示例 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" 不在字典中，所以无法进行转换。

**提示：**

*  `1 <= beginWord.length <= 10`
 *  `endWord.length == beginWord.length`
 *  `1 <= wordList.length <= 5000`
 *  `wordList[i].length == beginWord.length`
 *  `beginWord`、`endWord` 和 `wordList[i]` 由小写英文字母组成
 *  `beginWord != endWord`
 *  `wordList` 中的所有字符串 **互不相同**

**题解**

对于状态转移中存在环的，那么求最短路径一定是 BFS + visit 标志数组 + level 计数

*  标志数组用来决定是否把某元素继续加入队列
 *  对于 DFS 来说，用标志数组来递归，碰到有环（无向图、有向图存在闭合多边形）的情况，如果通过标志数组直接返回的话， 将无法获得该节点的返回值（因为该节点还正在向下递归，但是又绕回来了，没有机会递归到底再回溯）

**注意：对于图的 BFS 来说，仅适用于无权图（即可以理解为每个节点的值为 1），如果是有权图（即每个节点里的值不同），那么就不能用 BFS，必须使用 Floyd 算法（动态规划算法，适用于有向图与无向图）**

public class Solution { 
    
        public int ladderLength(String beginWord, String endWord, List<String> wordList) { 
           LinkedList<String> queue = new LinkedList<>();
           queue.addLast(beginWord);
    
           int level = 1;
           HashSet<String> isVisit = new HashSet<>();
    
           while(queue.size() != 0){ 
               int levelSize = queue.size();
               for(int i = 0 ; i < levelSize ; i ++){ 
                   String word = queue.pop();
                   if(word.equals(endWord)){ 
                       return level;
                   }
    
                   for(int j = 0 ; j < wordList.size() ; j ++){ 
                       String w = wordList.get(j);
                       if(isVisit.contains(w)){ 
                           continue;
                       }
    
                       int dif = 0;
                       for(int k = 0 ;  k < word.length() ; k ++){ 
                           if(word.charAt(k) != w.charAt(k)){ 
                               dif ++;
                           }
                       }
    
                       if(dif == 1){ 
                           isVisit.add(w);
                           queue.addLast(w);
                       }
                   }
               }
    
               level ++;
           }
    
           return 0;
        }
    
        
    }

##### 有权图最短路径：Floyd 算法 #####

*  每个状态有的决定因素有两个，起始节点和终止节点（即 dp 数组是二维的）
 *  状态转移方程
    
    `fun(i , j) = max([i , j] , max([i , k] + [k , j]))`

typedef struct          {         
        char vertex[VertexNum];                                //顶点表 
        int edges[VertexNum][VertexNum];                       //邻接矩阵（对于两个边不可达的是无穷） 
        int n,e;                                               //图中当前的顶点数和边数 
    }MGraph; 
    
    void Floyd(MGraph g){ 
        int A[MAXV][MAXV]; // dp 数组
        int path[MAXV][MAXV]; // 路径（跟 dp 数组对应的，每个节点的下一步）
        int i,j,k,n=g.n;
        
        // 初始化 dp 数组（对于 dp 问题大多数都要初始化，或者多开辟一行）。
        for(i=0;i<n;i++){ 
            for(j=0;j<n;j++){  　　
                A[i][j]=g.edges[i][j];
                path[i][j]=-1;
            }
        }
        
        // 常规动态规划的模板
        // 至于这个 k 为什么放最外层，根据状态方程 dij(k) = min(dij(k-1) , dik(k-1) + dkj(k-1)), k-1 代表不包含k时的值，
        // 可以理解为 k 是每次增加一个（即中间节点每次加一个），把 i 和 j 看成一个整体（代表 i 到 j）的长度。
        // 对于常规的，在状态转移方程里有 3 个变量，但是状态的决定属性只有两个，那么把状态多的那个属性放在最外层，把里面的二维看作一个整体，每次外层增加一个然后选择最优。
        // 跟背包问题其实很像，对于 k 都是只能选一次，因为一旦选了 k 作中转，后面如果再选 k 作中转，那么会形成环，是肯定不可达 i 或者 j 的，所以问题就变成了每个节点只可以选一次，那么只有选不选这两种情况，所以就还是背包问题。
        for(k=0;k<n;k++){  
            for(i=0;i<n;i++){ 
                for(j=0;j<n;j++){ 
                    if(A[i][j]>(A[i][k]+A[k][j])){                    　　
                        A[i][j]=A[i][k]+A[k][j];
                        path[i][j]=k;
                    } 
                }
            } 
        } 
        
    }

#### 小结 ####

对于状态转移无环：DFS（记忆化搜索）

对于状态转移有环

*  无权：BFS（队列 + isVisit 标志）
 *  有权：动态规划（把 i j 看成一个整体，i 和 j 代表两个顶点，可以是任意两个对象）
    
     *  其实对于常规的三层 for 的动态规划，基本都满足可以把其中两维看作一个整体

[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[107. _ II]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
[103.]: https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
[199.]: https://leetcode-cn.com/problems/binary-tree-right-side-view/
[127.]: https://leetcode-cn.com/problems/word-ladder/