CHIEMINCHAN'S BLOG

# 👉 遍历和递归

# 遍历

# 二叉树的遍历方式

  1. 按照顺序规则方式

先序遍历（preorder）：根->左->右
中序遍历（inorder）：左->根->右
后序遍历（postorder）：左->右->根
层次遍历：扫描式

  1. 按照实现规则方式

递归遍历（先、中、后序遍历）
迭代遍历（层次遍历）

# 深度优先搜索 DFS （先序遍历+栈）

DFS 是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。

  • DFS 的特点是试图穷举所有完整的路径，往往会使用递归来模拟入栈和出栈的过程。

  • 二叉树的先序遍历正是深度优先搜索思想的递归实现。可以说深度优先搜索过程就类似于树的先序遍历、是树的先序遍历的推广。

  • DFS 的本质为栈

1） 函数调用底层由栈实现：
函数调用的上下文就会被 push 进函数调用栈中；待函数执行完毕后，对应的上下文又会从调用栈中被 pop 出来。

2）DFS 作为一种思想，它和树的递归遍历一脉相承、却并不能完全地画上等号——DFS 的解题场景其实有很多，其中有一类会要求我们记录每一层递归式里路径的状态，此时就会强依赖栈结构。

function DFS(root) {
    // 边界情况停止递归
    if (!root) return;

    // 递归式
    console.log(root.val);
    dfs(root.left);
    dfs(root.right);
}

# 广度优先搜索 BFS （层次遍历+队列）

广度优先遍历是从根节点开始，沿着图的宽度遍历节点，如果所有的节点均被访问过，则算法终止。

BFS 着重关注眼下自己能够直接到达的所有坐标，而非 DFS 的“不撞南墙不回头”。

BFS 的核心思想和二叉树的层次遍历类似，而其中会有两个规律：

1）每访问完毕一个坐标，这个坐标在后续的遍历中都不会再被用到了，也就是说它可以被丢弃掉。
2）站在某个确定坐标的位置上，我们所观察到的可直接抵达的坐标，是需要被记录下来的，因为后续的遍历还要用到它们。

丢弃已访问的坐标、记录新观察到的坐标，这个顺序毫无疑问符合了“先进先出”的原则，因此整个 BFS 算法的实现过程，和队列有着密不可分的关系。

function BFS(root) {
    const result = [];

    if (!root) return result;

    // 初始化队列queue
    const queue = [];

    // 根结点先入队
    queue.push(root);

    while (queue.length) {
        // 取出队头
        const top = queue.shift();

        // 此处可以处理一些和 top 相关的逻辑，比如记录它对应的信息、检查它的属性等等
        // 比如访问top并记录
        result.push(top.val);

        // 注意这里也可以不用 for 循环，视题意而定
        // for(检查 top 元素出发能够遍历到的所有元素)  {
        // queue.push(top能够直接抵达的元素)
        // }

        // 如果左子树存在，左子树入队
        if (top.left) {
            queue.push(top.left);
        }
        // 如果右子树存在，右子树入队
        if (top.right) {
            queue.push(top.right);
        }
    }

    return result;
}

# 常见问题

# 岛屿问题

思路参考：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

# 递归

# 树递归遍历的三种方式

以后只要分析出重复的逻辑（排除掉类似数组遍历这种简单粗暴的重复），你都需要把递归从你的大脑内存里调度出来、将其列为“可以一试”的解法之一；

只要想到递归，立刻回忆 DFS 思想、然后尝试套解题模板。递归思想：1.分析重复动作，确认重复的递归式；2.确认递归边界（递归终点）。

# 常见问题类型

# 全排列（固定的坑位）

# 组合问题（变化的坑位）

# 限定组合问题（及时回溯，即为“剪枝” ）

# 回溯

回溯是指一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。
“回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。”（看着有点 DFS 的意思）

# 递归与回溯问题——解题模板总结

  1. 什么时候用（场景）

（1）题目中暗示了一个或多个解，并且要求我们详尽地列举出每一个解的内容时，一定要想到 DFS、想到递归回溯。
（2）题目经分析后，可转化为树形逻辑模型求解。

  1. 为什么用（依据）

递归与回溯的过程，本身就是穷举的过程。解是基于穷举思想、对搜索树进行恰当地剪枝后得来的。

在深度优先搜索中，有时我们会去掉一些不符合题目要求的、没有作用的答案，进而得到正确答案。这个丢掉答案的过程，形似剪掉树的枝叶，所以这一方法被称为“剪枝”。

还有一种情况是不问解的内容，只问解的个数。这类问题往往不用 DFS 来解，而是用动态规划。

  1. 怎么用（实现步骤）

一个模型——树形逻辑模型；两个要点——递归式和递归边界。

树形逻辑模型的构建，关键在于找“坑位”，一个坑位就对应树中的一层，每一层的处理逻辑往往是一样的，这个逻辑就是递归式的内容。

递归边界，要么在题目中约束得非常清楚、要么默认为“坑位”数量的边界。

根据以上规律，总结出的大概代码形式：

function getResults(arg) {
    // 前期初始化的准备工作

    // 存储每条路径
    const path = [];

    // 进入dfs
    dfs(起点);

    const dfs = (递归参数) => {
        if (递归边界) {
            根据题意作出的边界逻辑处理;
            return;
        }

        // 递归式，注意这里也可能不是 for，视题意决定
        for(遍历每个坑位可选的值){

          path.push(当前选中值)

          处理坑位本身的相关逻辑

          path.pop()
        }
    };
}

回溯例题：

【中等】60-第 k 个排列

【中等】79-单词搜索

【中等】332-重新安排行程

【困难】51-N 皇后

  • 精通

【困难】37-解数独

← 双指针 →