算法刻意练习之DFS/BFS/双向BFS/剪枝

偏执的太偏执、 2022-12-08 14:20 104阅读 0赞

## 1 初级搜索 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]

### 1.1 特点 ###

（1）如果遍历的数据结构本身没有任何特点，就遍历所有的节点，同时保证

*  **每个点访问一次，且仅访问一次，最后找到结果**；

（2）对于节点的访问顺序不限，可分为

*  **深度优先 depth first search**；
 *  **广度优先 breadth first search**；

（3）在树（图/状态集）中寻找特定结点

public class TreeNode { 
    	public int val; 
    	public TreeNode left, right; 
    	public TreeNode(int val) { 
     		this.val = val; 
    		this.left = null; 
     		this.right = null; 
    	} 
    }

## 2 深度优先遍历-DFS(Depth-First-Search) ##

### 2.1 特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]

### 2.2 模板代码 ###

#### 2.2.1 递归 ####

/**
         * 107. 二叉树的层次遍历 -- DFS深度遍历-递归
         *
         * 思想：每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。
         *
         * 时间复杂度：O(n)，每个点进队出队各一次，故渐进时间复杂度为 O(n)；
         * 空间复杂度：O(h)，h 是树的高度。
         *
         * @param root
         * @return
         */
    fun levelOrder1(root: TreeNode?): List<List<Int>>? {
            // 存放最终结果的集合
            val res: MutableList<MutableList<Int>> = mutableListOf()
            if (root == null) return res
    
            dfsLevel(1, root, res)
            return res
        }

fun dfsLevel(index: Int, root: TreeNode?, res: MutableList<MutableList<Int>>) {
            if (root == null) return
    
            // 假设res是[[1],[2,3]]，index是3，就再插入一个空list放到res中
            if (res.size < index) res.add(mutableListOf())
    
            // 将当前节点的值加入到res中，index-1代表当前层，假设index-1是3-1=2，节点值是6。res是[[1],[2,5],[3,4]]，加入后res就变为[[1],[2,5],[3,4,6]]
            res[index - 1].add(root.`val`)
    
            // 递归的处理左子树，右子树，同时将层数index+1
            if (root.left != null) dfsLevel(index + 1, root.left, res)
    
            if (root.right != null) dfsLevel(index + 1, root.right, res)
        }

#### 2.2.2 迭代 ####

/**
         * 144. 二叉树的前序遍历：递归
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间，递归深度会达到 n 层。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/144-er-cha-shu-de-qian-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun preorderTraversal(root: TreeNode?): List<Int?>? {
            if (root == null) return list
    
            list.add(root.`val`)
    
            preorderTraversal(root.left)
    
            preorderTraversal(root.right)
    
            return list
        }

/**
         * 94. 二叉树的中序遍历：递归
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间，递归深度会达到 n 层。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/94-er-cha-shu-de-zhong-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun inorderTraversal(root: TreeNode?): List<Int> {
            if (root == null) return list
    
            inorderTraversal(root.left)
    
            list.add(root.`val`)
    
            inorderTraversal(root.right)
    
            return list
        }

/**
         * 145. 二叉树的后序遍历：递归
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间，递归深度会达到 n 层。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/145-er-cha-shu-de-hou-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun postorderTraversal(root: TreeNode?): List<Int> {
            if (root == null) return list
    
            postorderTraversal(root.left)
    
            postorderTraversal(root.right)
    
            list.add(root.`val`)
    
            return list
        }

/**
         * 144. 二叉树的前序遍历：迭代
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/144-er-cha-shu-de-qian-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun preorderTraversal1(root: TreeNode?): List<Int> {
            val res: MutableList<Int> = mutableListOf()
            val stack: Deque<TreeNode?> = LinkedList()
    
            if (root == null) return res else stack.push(root)
    
            while (!stack.isEmpty()) {
                // 将根节点弹出，如果为标记null，则是将空节点弹出即可；如果不为null，下面再将根节点添加到栈中
                val node = stack.pop()
                if (node != null) {
                    // 添加右节点
                    if (node.right != null) stack.push(node.right)
                    // 添加左节点
                    if (node.left != null) stack.push(node.left)
    
                    // 添加根节点
                    stack.push(node)
                    // 根节点访问过，但还没有处理，需要做一下标记null
                    stack.push(null)
                } else {
                    // 遇到标记，弹出栈顶元素，加入到集合中
                    res.add(stack.pop()!!.`val`)
                }
            }
            return res
        }

/**
         * 94. 二叉树的中序遍历：迭代
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/94-er-cha-shu-de-zhong-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun inorderTraversal1(root: TreeNode?): List<Int> {
            val res: MutableList<Int> = mutableListOf()
            val stack: Deque<TreeNode?> = LinkedList()
    
            if (root == null) return res else stack.push(root)
    
            while (!stack.isEmpty()) {
                // 将根节点弹出，如果为标记null，则是将空节点弹出即可；如果不为null，下面再将根节点添加到栈中
                val node = stack.pop()
                if (node != null) {
                    // 添加右节点
                    if (node.right != null) stack.push(node.right)
                    // 添加根节点
                    stack.push(node)
                    // 根节点访问过，但还没有处理，需要做一下标记null
                    stack.push(null)
                    // 添加左节点
                    if (node.left != null) stack.push(node.left)
                } else {
                    // 遇到标记，弹出栈顶元素，加入到集合中
                    res.add(stack.pop()!!.`val`)
                }
            }
            return res
        }

/**
         * 145. 二叉树的后序遍历：迭代
         *
         * 时间复杂度：O(n)，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。
         * 空间复杂度：O(n)，空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。
         *
         * 题解：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/145-er-cha-shu-de-hou-xu-bian-li-by-chen-li-guan/
         * @param root
         * @return
         */
        fun postorderTraversal1(root: TreeNode?): List<Int> {
            val res: MutableList<Int> = mutableListOf()
            val stack: Deque<TreeNode?> = LinkedList()
    
            if (root == null) return res else stack.push(root)
    
            while (!stack.isEmpty()) {
                // 将根节点弹出，如果为标记null，则是将空节点弹出即可；如果不为null，下面再将根节点添加到栈中
                val node = stack.pop()
                if (node != null) {
                    // 添加根节点
                    stack.push(node)
                    // 根节点访问过，但还没有处理，需要做一下标记null
                    stack.push(null)
                    // 添加右节点
                    if (node.right != null) stack.push(node.right)
                    // 添加左节点
                    if (node.left != null) stack.push(node.left)
                } else {
                    // 遇到标记，模拟执行方法内部操作
                    res.add(stack.pop()!!.`val`)
                }
            }
            return res
        }

## 3 广度优先遍历-BFS(Breadth-First-Search) ##

### 3.1 特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]

### 3.2 DFS和BFS对比 ###

![在这里插入图片描述][20200919233715904.png_pic_center]

### 3.3 模板代码-迭代 ###

/**
         * 107. 二叉树的层次遍历 -- 方法一：BFS广度遍历-迭代
         *
         * 时间复杂度：O(n)，每个点进队出队各一次，故渐进时间复杂度为 O(n)；
         * 空间复杂度：O(n)，队列中元素的个数不超过 nn 个，故渐进空间复杂度为 O(n)。
         *
         * @param root
         * @return
         */
        fun levelOrder(root: TreeNode?): List<List<Int>>? {
            // 1.1 创建一个存放最终结果的集合 和 存放节点的队列
            val res: MutableList<List<Int>> = mutableListOf()
            val queue: Queue<TreeNode> = LinkedList()
    
            // 1.2 根节点不==null，将根节点放入其中
            if (root == null) return res else queue.offer(root)
    
            // 2.1 遍历每一层前，下层的队列不为空，继续遍历
            while (queue.isNotEmpty()) {
                val list: MutableList<Int> = mutableListOf()
                // 2.2 将这一层的元素全部取出，因为长度已确定，不会遍历新加入的左右节点
                for (i in 0 until queue.size) {
                    val node = queue.poll()
                    // 2.3 添加遍历后的元素到集合中
                    list.add(node.`val`)
    
                    // 3 如果节点的左右孩子不为空，放入队列
                    if (node.left != null) queue.offer(node.left)
                    if (node.right != null) queue.offer(node.right)
                }
    
                // 4 赋值到集合中
                res.add(list)
            }
    
            return res
        }

## 4 双向BFS ##

### 4.1 单向BFS ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]

### 4.2 双向BFS ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]

### 4.3 经典案例 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]

/**
         * 127. 单词接龙  方法一：双向BFS
         *
         * 时间复杂度：O(M×N)，其中 MM 是单词的长度N是单词表中单词的总数。与单向搜索相同的是，找到所有的变换需要M * N次操作。
         *          但是搜索时间会被缩小一半，因为两个搜索会在中间某处相遇。
         * 空间复杂度：O(M×N)，要在all_combo_dict字典中记录每个单词的M个通用状态，这与单向搜索相同。
         *          但是因为会在中间相遇，所以双向搜索的搜索空间变小。
         *
         * https://leetcode-cn.com/problems/word-ladder/solution/127-dan-ci-jie-long-by-chen-li-guan/
         * @param beginWord
         * @param endWord
         * @param wordList
         * @return
         */
        fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
            if (!wordList.contains(endWord)) return 0
    
            // 1 先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
            val wordList = wordList as MutableList<String>
            wordList.add(beginWord)
            val allWordSet: Set<String> = HashSet(wordList)
    
            // 2.1 创建一个队列，将新访问到的节点放入其中
            var queue1: Queue<String> = LinkedList()
            var queue2: Queue<String> = LinkedList()
            // 2.2 已经访问过的 word 添加到 visited 哈希表里
            var visited1: MutableSet<String?> = HashSet()
            var visited2: MutableSet<String?> = HashSet()
            queue1.offer(beginWord)
            queue2.offer(endWord)
            visited1.add(beginWord)
            visited2.add(endWord)
            // 2.3 计算已遍历节点总数
            var count = 0
    
            // 3.1 执行双向 BFS，左右交替扩散的步数之和为所求
            while (queue1.isNotEmpty() && queue2.isNotEmpty()) {
                // 3.2 从AB两个方向的中，选择当前节点更少的队列，在另一个方向进行层序遍历（这种方式搜索的这一层单词数量会更小一些）
                if (queue1.size > queue2.size) {
                    val temp = queue1
                    queue1 = queue2
                    queue2 = temp
                    val v = visited1
                    visited1 = visited2
                    visited2 = v
                }
    
                // 3.3 开始遍历每一层的每个字符串
                count++
                var size1: Int = queue1.size
                while (size1-- > 0) {
    
                    // 4.1 轮流替换一个字符串的每个字符后遍历
                    val chars = queue1.poll().toCharArray()
                    for (i in chars.indices) {
                        // 4.2 保存第i位的字符
                        val temp = chars[i]
    
                        // 4.3 用a~z替换当前字符，再对比新字符串，比较26次；
                        // 因为单词是由a~z字符组成，可以遍历当前单词能转换成的所有单词，判断其是否包含在候选单词中
                        var ch = 'a'
                        while (ch <= 'z') {
                            chars[i] = ch
                            val newString = String(chars)
                            // 4.4 已经访问过了，跳过
                            if (visited1.contains(newString)) {
                                ch++
                                continue
                            }
    
                            // 4.5 两端遍历相遇，结束遍历，返回count
                            if (visited2.contains(newString)) {
                                return count + 1
                            }
                            // 4.6 如果单词在列表中存在，将其添加到队列，并标记为已访问
                            if (allWordSet.contains(newString)) {
                                queue1.offer(newString)
                                visited1.add(newString)
                            }
                            ch++
                        }
    
                        // 4.7 恢复第i位的字符，为其他字符替换准备
                        chars[i] = temp
                    }
                }
            }
            return 0
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ce715d2948454da0bca7210c2f929140.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/af1135c3338f44839269955022f0047c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/13003fbac67848e29efee151ef12fd7c.png
[20200919233715904.png_pic_center]: /images/20221123/f98bf7ceceee432a8254c45276e17a2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/4cf7044416564f3ab968df87dbc22c18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/d236310157bd41389a1b95f0ecdd6417.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/86a3cfa234814a688121546e08121c47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/0139c2e5582743bab9eec6d22fd2d241.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/fac3aadecb8a4e649ddbb98473e4ee9f.png