学习数据结构和算法的框架思维

这几年在我自己不断刷题、思考和写教程的过程中，我对算法的理解也是在逐渐加深，所以今天再写一篇，融合了多篇旧文，把我多年的经验和思考浓缩成 7000 字，分享给大家。

本文主要有两部分，一是谈我对数据结构和算法本质的理解，二是概括各种常用的算法。全文没有什么硬核的代码，都是我的经验之谈，也许没有多么高大上，但肯定能帮你少走弯路，更透彻地理解和掌握算法。

真正理解上面几句话，不仅本文 7000 字都不用看了，乃至本站的几十篇算法教程和 500 道习题都不用做了。

如果不理解，那么我就用下面的几千字，以及后面的几十篇文章和 500 道习题，来阐明上述的两句总结。大家在学习的时候，时刻品味这两句话，会大幅提高学习效率。

数据结构的存储方式

数据结构的存储方式只有两种：数组（顺序存储） 和 链表（链式存储）。

这句话怎么理解，不是还有哈希表、栈、队列、堆、树、图等等各种数据结构吗？

我们分析问题，一定要有递归的思想，自顶向下，从抽象到具体。你上来就列出这么多，那些都属于上层建筑，而数组和链表才是结构基础。因为那些多样化的数据结构，究其源头，都是在链表或者数组上的特殊操作，API 不同而已。

比如说 队列、栈 这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

图结构 的两种存储方式，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

哈希表 就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法 需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法 需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

树结构，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单，经典应用有 二叉堆；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如 二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

**数组**由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 $O(N)$。

**链表**因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 $O(1)$。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

数据结构的基本操作

对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。

数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改，这就是数据结构的使命。

如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

线性就是 for/while 迭代为代表，非线性就是递归为代表。再具体一步，无非以下几种框架：

数组遍历框架，典型的线性迭代结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

void traverse(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        // 迭代访问 arr[i]
    }
}

def traverse(arr: List[int]):
    for i in range(len(arr)):
        # 迭代访问 arr[i]

func traverse(arr []int) {
    for i := 0; i < len(arr); i++ {
        // 迭代访问 arr[i]
    }
}

var traverse = function(arr) {
  for (var i = 0; i < arr.length; i++) {
    // 迭代访问 arr[i]
  }
}

链表遍历框架，兼具迭代和递归结构：

// 基本的单链表节点
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

// 基本的单链表节点
class ListNode {
    public:
        int val;
        ListNode* next;
};

void traverse(ListNode* head) {
    for (ListNode* p = head; p != nullptr; p = p->next) {
        // 迭代访问 p->val
    }
}

void traverse(ListNode* head) {
    // 递归访问 head->val
    traverse(head->next);
}

# 基本的单链表节点
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def traverse(head: ListNode) -> None:
    p = head
    while p is not None:
        # 迭代访问 p.val
        p = p.next

def traverse(head: ListNode) -> None:
    # 递归访问 head.val
    traverse(head.next)

// 基本的单链表节点
type ListNode struct {
    val int
    next *ListNode
}

func traverse(head *ListNode) {
    for p := head; p != nil; p = p.next {
        // 迭代访问 p.val
    }
}

func traverse(head *ListNode) {
    // 递归访问 head.val
    traverse(head.next)
}

// 基本的单链表节点
class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function traverse(head) {
    for (var p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

function traverse(head) {
    // 递归访问 head.val
    traverse(head.next);
}

二叉树遍历框架，典型的非线性递归遍历结构：

// 基本的二叉树节点
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// 基本的二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void traverse(TreeNode* root) {
    traverse(root->left);
    traverse(root->right);
}

# 基本的二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def traverse(root: TreeNode):
    traverse(root.left)
    traverse(root.right)

// 基本的二叉树节点
type TreeNode struct {
    val int
    left *TreeNode
    right *TreeNode
}

// 后序遍历二叉树
func traverse(root *TreeNode) {
    if root != nil {
        traverse(root.left)
        traverse(root.right)
    }
}

// 基本的二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

var traverse = function(root) {
  if (root === null) return;
  traverse(root.left);
  traverse(root.right);
};

你看二叉树的递归遍历方式和链表的递归遍历方式，相似不？再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树你会不会遍历？

二叉树框架可以扩展为 N 叉树的遍历框架：

// 基本的 N 叉树节点
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

// 基本的 N 叉树节点
class TreeNode {
public:
    int val;
    vector<TreeNode*> children;
};

void traverse(TreeNode* root) {
    for (TreeNode* child : root->children)
        traverse(child);
}

# 基本的 N 叉树节点
class TreeNode:
    val: int
    children: List[TreeNode]

def traverse(root: TreeNode) -> None:
    for child in root.children:
        traverse(child)

// 基本的 N 叉树节点
type TreeNode struct {
    val int
    children []*TreeNode
}

func traverse(root *TreeNode) {
    for _, child := range root.children {
        traverse(child)
    }
}

// 基本的 N 叉树节点
var TreeNode = function(val, children) {
  this.val = val;
  this.children = children;
};

// 遍历 N 叉树
var traverse = function(root) {
  for (var i = 0; i < root.children.length; i++) {
    traverse(root.children[i]);
  }
};

N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，图结构遍历 中有具体讲解。

所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了。

算法的本质

如果要让我一句话总结，我想说算法的本质就是「穷举」。

这么说肯定有人要反驳了，真的所有算法问题的本质都是穷举吗？没有例外吗？

例外肯定是有的，比如 一行代码就能解决的算法题，这些题目类似脑筋急转弯，都是通过观察，发现规律，然后找到最优解法，不过这类算法问题较少，不必特别纠结。再比如，密码学算法、机器学习算法，它们的本质确实不是穷举，而是数学原理的编程实现，所以这类算法的本质是数学，不在我们所探讨的「数据结构和算法」的范畴之内。

顺便强调下，「算法工程师」做的这个「算法」，和「数据结构与算法」中的这个「算法」完全是两码事，免得一些初学读者误解。

对前者来说，重点在数学建模和调参经验，计算机真就只是拿来做计算的工具而已；而后者的重点是计算机思维，需要你能够站在计算机的视角，抽象、化简实际问题，然后用合理的数据结构去解决问题。

所以，你千万别以为学好了数据结构和算法就能去做算法工程师，也不要以为只要不做算法工程师就不需要学习数据结构和算法。

坦白说，大部分开发岗位工作中都是基于现成的开发框架做事，不怎么会碰到底层数据结构和算法相关的问题，但另一个事实是，只要你想找技术相关的岗位，数据结构和算法的考察是绕不开的，因为这块知识点是公认的程序员基本功。

为了区分，不妨称算法工程师研究的算法为「数学算法」，称刷题面试的算法为「计算机算法」，我写的内容主要聚焦的是「计算机算法」。

这样解释应该很清楚了吧，我猜大部分人的目标是通过算法笔试，找一份开发岗位的工作，所以你真的不需要有多少数学基础，只要学会用计算机思维解决问题就够了。

其实计算机思维也没什么高端的，你想想计算机的特点是啥？不就是快嘛，你的脑回路一秒只能转一圈，人家 CPU 转几万圈无压力。所以计算机解决问题的方式大道至简，就是穷举。

我记得自己刚入门的时候，也觉得计算机算法是一个很高大上的东西，每见到一道题，就想着能不能推导出一个什么数学公式，啪的一下就能把答案算出来。

比如你和一个没学过计算机算法的人说你写了个计算排列组合的算法，他大概以为你发明了一个公式，可以直接算出所有排列组合。但实际上呢？没什么高大上的公式，我会在 回溯算法秒杀排列组合子集问题 讲解，其实就是把排列组合的所有可能抽象成一棵多叉树结构，然后你写代码去遍历这棵树，把所有的结果收集起来罢了。这有啥神奇的？

对计算机算法的误解也许是以前学数学留下的「后遗症」，数学题一般都是你仔细观察，找几何关系，列方程，然后算出答案。如果说你需要进行大规模穷举来寻找答案，那大概率是你的解题思路出问题了。

而计算机解决问题的思维恰恰相反：有没有什么数学公式就交给你们人类去推导吧，如果能找到一些巧妙的定理那最好，但如果找不到，那就穷举呗，反正只要复杂度允许，没有什么答案是穷举不出来的。理论上讲只要不断随机打乱一个数组，总有一天能得到有序的结果呢！当然，这绝不是一个好算法，因为鬼知道它要运行多久才有结果。

技术岗笔试面试考的那些算法题，求个最大值最小值什么的，你怎么求？把所有可行解穷举出来就能找到最值了呗，说白了不就这么点事儿么。

穷举的难点

不同类型的题目，难点是不同的，有的题目难在「如何穷举」，有的题目难在「如何聪明地穷举」。

什么算法的难点在「如何穷举」呢？一般是递归类问题，比方说回溯算法、动态规划系列算法。

先说回溯算法，就拿我们高中学过的排列组合问题举例，我们当时都可以找到规律在草稿纸上推导排列组合：根据第一位可能的选择，先固定第一位，然后看第二位有哪些可能的选择，然后固定第二位... 以此类推，但如果未经训练，你很难用代码来穷举所有排列组合，因为你很难把这个手动穷举的过程抽象成程序化的规律。

首先，你要把排列组合问题抽象成一棵树，其次你要精确地使用代码遍历这棵树的所有节点，不能漏不能多，才能写出正确的代码。在后面的章节中，我会先介绍 回溯算法核心框架，然后在 回溯算法解决子集排列组合问题 一次性解决所有子集排列组合问题。

动态规划比回溯算法更难一点。它俩本质上都是穷举，但思考模式不同，回溯算法是「遍历」的思维，而动态规划是「分解问题」的思维。

所以你知道为啥我说动态规划这类问题的难点在于「如何穷举」了吧？一个脑瓜正常的人，本来就不会用这种奇怪的思维方式来思考问题，但这种思维结合计算机就是杀手锏，所以你要练，练好了，随心所欲写算法，咋写都是对的。

我在 动态规划核心框架 阐述了动态规划系列问题的解题过程，无非就是先写出暴力穷举解法（状态转移方程），加个备忘录就成自顶向下的递归解法了，再改一改就成自底向上的递推迭代解法了，动态规划的降维打击 里也讲过如何利用空间压缩技巧优化动态规划算法的空间复杂度。

其中加备忘录、空间压缩技巧都是「如何聪明地穷举」的范畴，套路固定，不是难点。你亲自去做动态规划的题目就会发现，自己根本想不出状态转移方程，即第一步的暴力解法都写不出来，所以说找状态转移方程（如何穷举）才是难点。

我专门写了 动态规划设计方法：数学归纳法 这篇文章，告诉你穷举的核心是数学归纳法，明确函数的定义，分解问题，然后利用这个定义递归求解子问题。

什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。

最简单的例子，比方说让你在有序数组中寻找一个元素，用一个 for 循环暴力穷举谁都会，但 二分搜索算法 就是更聪明的穷举方式，拥有更好的时间复杂度。

还有后文 Union Find 并查集算法详解 告诉你一种高效计算连通分量的技巧，理论上说，想判断图中的两个节点是否连通，我用 DFS/BFS 暴力搜索（穷举）肯定可以做到，但人家 Union Find 算法硬是用数组模拟树结构，给你把连通性相关的操作复杂度给干到 $O(1)$ 了。

这就属于聪明地穷举，大佬们把这些技巧发明出来，你学过就会用，没学过恐怕很难想出这种思路。

再比如贪心算法技巧，后文 当老司机学会贪心算法 就告诉你，所谓贪心算法就是在题目中发现一些规律（专业点叫贪心选择性质），使得你不用完整穷举所有解就可以得出答案。

人家动态规划好歹是无冗余地穷举所有解，然后找一个最值，你贪心算法可好，都不用穷举所有解就可以找到答案，所以后文 贪心算法解决跳跃游戏 中贪心算法的效率比动态规划还高。当然，并不是所有问题都存在贪心选择性质让你投机取巧，所以全量穷举虽然朴实无华且枯燥，但真的是任何情况下都可以用的。

下面我概括性地列举一些常见的算法技巧，供大家学习参考。

数组/单链表系列算法

单链表常考的技巧就是双指针，属于「如何聪明地穷举」这一类，单链表双指针技巧汇总 全给你总结好了，会者不难，难者不会。

比如判断单链表是否成环，拍脑袋的暴力解是什么？就是用一个 HashSet 之类的数据结构来缓存走过的节点，遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间，这就是聪明地穷举嘛。

数组常用的技巧有也是双指针相关的技巧，也都属于「如何聪明地穷举」这一类。数组双指针技巧汇总 全给你总结好了，会者不难，难者不会。

首先说二分搜索技巧，可以归为两端向中心的双指针。如果让你在数组中搜索元素，一个 for 循环花 $O(N)$ 时间穷举肯定能搞定对吧，但是二分搜索告诉你，如果数组是有序的，它只要 $O(logN)$ 的复杂度，这不就是一种更聪明的搜索方式么。

二分搜索框架详解 给你总结了二分搜索代码模板，保证不会出现搜索边界的问题。二分搜索算法运用 给你总结了二分搜索相关题目的共性以及如何将二分搜索思想运用到实际算法中。

再说说 滑动窗口算法技巧，典型的快慢双指针。你用嵌套 for 循环花 $O(N^2)$ 的时间肯定可以穷举出所有子数组，也就必然可以找到符合题目要求的子数组。但是滑动窗口算法表示，在某些场景下，它可以用一快一慢两个指针，只需 $O(N)$ 的时间就可以找到答案，这就是更聪明地穷举方式。

滑动窗口算法框架详解 介绍了滑动窗口算法的适用场景以及通用代码模板，保你写出正确的代码。滑动窗口习题 中手把手带你运用滑动窗口框架解决各种问题。

最后说说 前缀和技巧 和 差分数组技巧。

如果频繁地让你计算子数组的和，每次用 for 循环去遍历肯定没问题，但前缀和技巧预计算一个 preSum 数组，就可以避免循环。

类似的，如果频繁地让你对子数组进行增减操作，也可以每次用 for 循环去操作，但差分数组技巧维护一个 diff 数组，也可以避免循环。

数组链表的技巧差不多就这些了，都比较固定，只要你都见过，运用出来的难度不算大，下面来说一说稍微有些难度的算法。

二叉树系列算法

老读者都知道，二叉树的重要性我之前说了无数次，因为二叉树模型几乎是所有高级算法的基础，尤其是那么多人说对递归的理解不到位，更应该好好刷二叉树相关题目。

二叉树心法（纲领篇） 说过，二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。

遍历的思维模式

什么叫通过遍历一遍二叉树得出答案？

就比如说计算二叉树最大深度这个问题让你实现 maxDepth 这个函数，你这样写代码完全没问题：

class Solution {

    // 记录最大深度
    int res = 0;
    // 记录当前遍历节点的深度
    int depth = 0;

    // 主函数
    int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    // 二叉树遍历框架
    void traverse(TreeNode root) {
        if (root == null) {
            // 到达叶子节点
            res = Math.max(res, depth);
            return;
        }
        // 前序遍历位置
        depth++;
        traverse(root.left);
        traverse(root.right);
        // 后序遍历位置
        depth--;
    }
}

class Solution {
public:

    // 记录最大深度
    int res = 0;
    // 记录当前遍历节点的深度
    int depth = 0;

    // 主函数
    int maxDepth(TreeNode* root) {
        traverse(root);
        return res;
    }

    // 二叉树遍历框架
    void traverse(TreeNode* root) {
        if (root == NULL) {
            // 到达叶子节点
            res = max(res, depth);
            return;
        }
        // 前序遍历位置
        depth++;
        traverse(root->left);
        traverse(root->right);
        // 后序遍历位置
        depth--;
    }
};

class Solution:
    def __init__(self):
        # 记录最大深度
        self.res = 0
        # 记录当前遍历节点的深度
        self.depth = 0
        
    def maxDepth(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.res
        
    def traverse(self, root: TreeNode) -> None:
        if not root:
            # 到达叶子节点
            self.res = max(self.res, self.depth)
            return
        # 前序遍历位置
        self.depth += 1
        self.traverse(root.left)
        self.traverse(root.right)
        # 后序遍历位置
        self.depth -= 1

func maxDepth(root *TreeNode) int {
    // res 记录最大深度
    // depth 记录当前遍历节点的深度
	res, depth := 0, 0
	traverse(root, &res, &depth)
	return res
}

func traverse(root *TreeNode, res *int, depth *int) {
	if root == nil {
		// 到达叶子节点
		*res = max(*res, *depth)
		return
	}
	// 前序遍历位置
	*depth++
	traverse(root.left, res, depth)
	traverse(root.right, res, depth)
	// 后序遍历位置
	*depth--
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var maxDepth = function(root) {
    // 记录最大深度
    let res = 0;
    // 记录当前遍历节点的深度
    let depth = 0;

    // 主函数
    function traverse(root) {
        if (root === null) {
            // 到达叶子节点
            res = Math.max(res, depth);
            return;
        }
        // 前序遍历位置
        depth++;
        traverse(root.left);
        traverse(root.right);
        // 后序遍历位置
        depth--;
    }

    traverse(root);
    return res;
};

这个逻辑就是用 traverse 函数遍历了一遍二叉树的所有节点，维护 depth 变量，在叶子节点的时候更新最大深度。

你看这段代码，有没有觉得很熟悉？能不能和回溯算法的代码模板对应上？

不信你照着 回溯算法核心框架 中全排列问题的代码对比下，backtrack 函数就是 traverse 函数，换汤不换药，整体逻辑非常类似：

class Solution {
    // 记录所有全排列
    List<List<Integer>> res = new LinkedList<>();
    // 记录当前正在穷举的排列
    LinkedList<Integer> track = new LinkedList<>();

    // track 中的元素会被标记为 true，避免重复使用
    boolean[] used;

    // 主函数，输入一组不重复的数字，返回它们的全排列
    List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        
        backtrack(nums);
        return res;
    }

    // 回溯算法核心框架，遍历回溯树，收集所有叶子节点上的全排列
    void backtrack(int[] nums) {
        // 到达叶子节点，track 中的元素就是一个全排列
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (used[i]) {

                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.add(nums[i]);
            used[i] = true;

            // 进入递归树的下一层
            backtrack(nums);
            
            // 取消选择
            track.removeLast();
            used[i] = false;
        }
    }
}

class Solution {
public:
    // 记录所有全排列
    vector<vector<int>> res;
    // 记录当前正在穷举的排列
    vector<int> track;

    // track 中的元素会被标记为 true，避免重复使用
    vector<bool> used;

    // 主函数，输入一组不重复的数字，返回它们的全排列
    vector<vector<int>> permute(vector<int>& nums) {
        used = vector<bool>(nums.size(), false);
        
        backtrack(nums);
        return res;
    }

    // 回溯算法核心框架，遍历回溯树，收集所有叶子节点上的全排列
    void backtrack(vector<int>& nums) {
        // 到达叶子节点，track 中的元素就是一个全排列
        if (track.size() == nums.size()) {
            res.push_back(track);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            // 排除不合法的选择
            if (used[i]) {
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            // 进入递归树的下一层
            backtrack(nums);
            
            // 取消选择
            track.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 记录所有全排列
        res = []
        # 记录当前正在穷举的排列
        track = []

        # track 中的元素会被标记为 true，避免重复使用
        used = [False] * len(nums)

        # 主函数，输入一组不重复的数字，返回它们的全排列
        def backtrack(nums):
            # 到达叶子节点，track 中的元素就是一个全排列
            if len(track) == len(nums):
                res.append(track[:])
                return

            for i in range(len(nums)):
                # 排除不合法的选择
                if used[i]:
                    # nums[i] 已经在 track 中，跳过
                    continue
                # 做选择
                track.append(nums[i])
                used[i] = True

                # 进入递归树的下一层
                backtrack(nums)

                # 取消选择
                track.pop()
                used[i] = False

        backtrack(nums)
        return res

func permute(nums []int) [][]int {
    // 记录所有全排列
    var res [][]int
    // 记录当前正在穷举的排列
    var track []int

    // track 中的元素会被标记为 true，避免重复使用
    used := make([]bool, len(nums))

    // 主函数，输入一组不重复的数字，返回它们的全排列
    backtrack(nums, &res, &track, used)
    return res
}

// 回溯算法核心框架，遍历回溯树，收集所有叶子节点上的全排列
func backtrack(nums []int, res *[][]int, track *[]int, used []bool) {
    // 到达叶子节点，track 中的元素就是一个全排列
    if len(*track) == len(nums) {
        tmp := make([]int, len(*track))
        copy(tmp, *track)
        *res = append(*res, tmp)
        return
    }

    for i := 0; i < len(nums); i++ {
        // 排除不合法的选择
        if used[i] {
            // nums[i] 已经在 track 中，跳过
            continue
        }
        // 做选择
        *track = append(*track, nums[i])
        used[i] = true

        // 进入递归树的下一层
        backtrack(nums, res, track, used)

        // 取消选择
        *track = (*track)[:len(*track)-1]
        used[i] = false
    }
}

var permute = function(nums) {
    // 记录所有全排列
    let res = [];
    // 记录当前正在穷举的排列
    let track = [];

    // track 中的元素会被标记为 true，避免重复使用
    let used = new Array(nums.length).fill(false);

    // 主函数，输入一组不重复的数字，返回它们的全排列
    function backtrack(nums) {
        // 到达叶子节点，track 中的元素就是一个全排列
        if (track.length === nums.length) {
            res.push(track.slice());
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (used[i]) {
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.push(nums[i]);
            used[i] = true;

            // 进入递归树的下一层
            backtrack(nums);

            // 取消选择
            track.pop();
            used[i] = false;
        }
    }

    backtrack(nums);
    return res;
};

你看这代码虽然多，但本质不就是多叉树的遍历吗？所以说回溯算法本质就是遍历多叉树，你只要能把问题抽象成树结构，就一定能用回溯算法解决。

分解问题的思维模式

那什么叫通过分解问题计算答案？

同样是计算二叉树最大深度这个问题，你也可以写出下面这样的解法：

// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	// 递归计算左右子树的最大深度
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	// 整棵树的最大深度就是左右子树的最大深度加一
	int res = Math.max(leftMax, rightMax) + 1;

	return res;
}

// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    // 递归计算左右子树的最大深度
    int leftMax = maxDepth(root->left);
    int rightMax = maxDepth(root->right);
    // 整棵树的最大深度就是左右子树的最大深度加一
    int res = max(leftMax, rightMax) + 1;

    return res;
}

# 定义：输入根节点，返回这棵二叉树的最大深度
def maxDepth(root: TreeNode) -> int:
    if root is None:
        return 0
    # 递归计算左右子树的最大深度
    leftMax = maxDepth(root.left)
    rightMax = maxDepth(root.right)
    # 整棵树的最大深度就是左右子树的最大深度加一
    res = max(leftMax, rightMax) + 1

    return res

// 定义：输入根节点，返回这棵二叉树的最大深度
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 递归计算左右子树的最大深度
    leftMax := maxDepth(root.left)
    rightMax := maxDepth(root.right)
    // 整棵树的最大深度就是左右子树的最大深度加一
    res := max(leftMax, rightMax) + 1

    return res
}

// 辅助函数
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 定义：输入根节点，返回这棵二叉树的最大深度
var maxDepth = function(root) {
    if (root == null) {
        return 0;
    }
    // 递归计算左右子树的最大深度
    let leftMax = maxDepth(root.left);
    let rightMax = maxDepth(root.right);
    // 整棵树的最大深度就是左右子树的最大深度加一
    let res = Math.max(leftMax, rightMax) + 1;

    return res;
};

你看这段代码，有没有觉得很熟悉？有没有觉得有点动态规划解法代码的形式？

不信你看 动态规划核心框架 中凑零钱问题的暴力穷举解法：

// 定义：输入金额 amount，返回凑出 amount 的最少硬币个数
int coinChange(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 递归计算凑出 amount - coin 的最少硬币个数
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        // 凑出 amount 的最少硬币个数
        res = Math.min(res, subProblem + 1);
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

// 定义：输入金额 amount，返回凑出 amount 的最少硬币个数
int coinChange(vector<int>& coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = INT_MAX;
    for (int coin : coins) {
        // 递归计算凑出 amount - coin 的最少硬币个数
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        // 凑出 amount 的最少硬币个数
        res = min(res, subProblem + 1);
    }

    return res == INT_MAX ? -1 : res;
}

def coinChange(coins: List[int], amount: int) -> int:
    # base case
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    # res 为凑出 amount 的最少硬币个数
    res = float('inf')
    for coin in coins:
        # 递归计算凑出 amount - coin 的最少硬币个数
        sub_problem = coinChange(coins, amount - coin)
        if sub_problem == -1:
            continue
        # 取最小值
        res = min(res, sub_problem + 1)

    return -1 if res == float('inf') else res

func coinChange(coins []int, amount int) int {
    // base case
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }

    res := math.MaxInt32
    for _, coin := range coins {
        // 递归计算凑出 amount - coin 的最少硬币个数
        subProblem := coinChange(coins, amount-coin)
        if subProblem == -1 {
            continue
        }
        // 凑出 amount 的最少硬币个数
        res = min(res, subProblem+1)
    }

    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

var coinChange = function(coins, amount) {
    // base case
    if (amount === 0) return 0;
    if (amount < 0) return -1;

    let res = Number.MAX_VALUE;
    for (let coin of coins) {
        // 递归计算凑出 amount - coin 的最少硬币个数
        let subProblem = coinChange(coins, amount - coin);
        if (subProblem === -1) continue;
        // 凑出 amount 的最少硬币个数
        res = Math.min(res, subProblem + 1);
    }

    return res === Number.MAX_VALUE ? -1 : res;
};

这个暴力解法加个 memo 备忘录就是自顶向下的动态规划解法，你对照二叉树最大深度的解法代码，有没有发现很像？

思路拓展

如果你感受到最大深度这个问题两种解法的区别，那就趁热打铁，我问你，二叉树的前序遍历怎么写？

我相信大家都会对这个问题嗤之以鼻，毫不犹豫就可以写出下面这段代码：

List<Integer> res = new LinkedList<>();

// 返回前序遍历结果
List<Integer> preorder(TreeNode root) {
    traverse(root);
    return res;
}

// 二叉树遍历函数
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序遍历位置
    res.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

vector<int> res;

// 返回前序遍历结果
vector<int> preorder(TreeNode* root) {
    traverse(root);
    return res;
}

// 二叉树遍历函数
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序遍历位置
    res.push_back(root->val);
    traverse(root->left);
    traverse(root->right);
}

class Solution:
    def __init__(self):
        # 创建一个链表作为结果容器
        self.res = []

    # 返回前序遍历结果
    def preorder(self, root: TreeNode) -> List[int]:
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root: TreeNode) -> None:
        if not root:
            return
        # 前序遍历位置
        self.res.append(root.val)
        self.traverse(root.left)
        self.traverse(root.right)

// 返回前序遍历结果
func preorder(root *TreeNode) []int {
    var res []int
    traverse(root, &res)
    return res
}

// 二叉树遍历函数
func traverse(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }
    // 前序遍历位置
    *res = append(*res, root.Val)
    traverse(root.Left, res)
    traverse(root.Right, res)
}

// 返回前序遍历结果
function preorder(root) {
    let res = [];

    // 二叉树遍历函数
    function traverse(root) {
        if (root === null) {
            return;
        }
        // 前序遍历位置
        res.push(root.val);
        traverse(root.left);
        traverse(root.right);
    }

    traverse(root);
    return res;
}

但是，你结合上面说到的两种不同的思维模式，二叉树的遍历是否也可以通过分解问题的思路解决呢？

可以观察一下二叉树前序遍历结果的特点：

你注意前序遍历的结果，根节点的值在第一位，后面接着左子树的前序遍历结果，最后接着右子树的前序遍历结果。

有没有体会出点什么来？其实完全可以重写前序遍历代码，用分解问题的形式写出来：

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
List<Integer> preorder(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    // 前序遍历的结果，root.val 在第一个
    res.add(root.val);
    // 后面接着左子树的前序遍历结果
    res.addAll(preorder(root.left));
    // 最后接着右子树的前序遍历结果
    res.addAll(preorder(root.right));
    return res;
}

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
vector<int> preorder(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) {
        return res;
    }
    // 前序遍历的结果，root->val 在第一个
    res.push_back(root->val);
    // 后面接着左子树的前序遍历结果
    vector<int> left = preorder(root->left);
    res.insert(res.end(), left.begin(), left.end());
    // 最后接着右子树的前序遍历结果
    vector<int> right = preorder(root->right);
    res.insert(res.end(), right.begin(), right.end());
    return res;
}

from typing import List

# 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
def preorder(root: TreeNode) -> List[int]:
    res = []
    if not root:
        return res
    # 前序遍历的结果，root.val 在第一个
    res.append(root.val)
    # 后面接着左子树的前序遍历结果
    res.extend(preorder(root.left))
    # 最后接着右子树的前序遍历结果
    res.extend(preorder(root.right))
    return res

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
func preorder(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    // 前序遍历的结果，root.val 在第一个
    res = append(res, root.val)
    // 后面接着左子树的前序遍历结果
    res = append(res, preorder(root.left)...)
    // 最后接着右子树的前序遍历结果
    res = append(res, preorder(root.right)...)
    return res
}

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
var preorder = function(root) {
    var res = [];
    if (root === null) {
        return res;
    }
    // 前序遍历的结果，root.val 在第一个
    res.push(root.val);
    // 后面接着左子树的前序遍历结果
    res = res.concat(preorder(root.left));
    // 最后接着右子树的前序遍历结果
    res = res.concat(preorder(root.right));
    return res;
};

你看，这就是用分解问题的思维模式写二叉树的前序遍历，如果写中序和后序遍历也是类似的。

层序遍历

除了动归、回溯（DFS）、分治，还有一个常用算法就是 BFS 了，BFS 算法核心框架 就是根据下面这段二叉树的层序遍历代码改装出来的：

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    int depth = 1;
    // 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();

            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
int levelTraverse(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);

    int depth = 0;
    // 从上到下遍历二叉树的每一层
    while (!q.empty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
    return depth;
}

# 输入一棵二叉树的根节点，层序遍历这棵二叉树
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = collections.deque()
        q.append(root)
        res = []
        while q:
            sz = len(q)
            tmp = []
            for i in range(sz):
                cur = q.popleft()
                tmp.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(tmp)
        return res

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
func levelTraverse(root *TreeNode) {
    if root == nil {
        return
    }

    q := make([]*TreeNode, 0)
    q = append(q, root)
    depth := 1

    // 从上到下遍历二叉树的每一层
    for len(q) > 0 {
        sz := len(q)

        // 从左到右遍历每一层的每个节点
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]

            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right) 
            }
        }
        depth++
    }
}

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
var levelTraverse = function(root) {
    if (root == null) return 0;
    var q = [];
    q.push(root);

    var depth = 1;
    // 从上到下遍历二叉树的每一层
    while (q.length > 0) {
        var sz = q.length;
        // 从左到右遍历每一层的每个节点
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();

            if (cur.left != null) {
                q.push(cur.left);
            }
            if (cur.right != null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
}

更进一步，图论相关的算法也是二叉树算法的延续。

比如 图论基础，环判断和拓扑排序 和 二分图判定算法 就用到了 DFS 算法；再比如 Dijkstra 算法模板，就是改造版 BFS 算法加上一个类似 dp table 的数组。

好了，说的差不多了，上述这些算法的本质都是穷举二（多）叉树，有机会的话通过剪枝或者备忘录的方式减少冗余计算，提高效率，就这么点事儿。

最后总结

很多读者问我什么刷题方式是正确的，我认为正确的刷题方式应该是刷一道题能获得刷十道题的效果，不然力扣现在 2000 道题目，你都打算刷完么？

那么怎么做到呢？要有框架思维，学会提炼重点，寻找那个不变的东西。一个算法技巧可以包装出一万道题，如果你能一眼看穿它们的本质，那么一万道题等于一道，何必浪费时间去做呢？

这就是框架的力量，能够保证你在快睡着的时候，依然能写出正确的程序；就算你啥都没学过，就这种思维方法，都能比别人高一个维度。

授人以鱼不如授人以渔，算法真的没啥难的，只要有心，谁都可以学好。我希望你能在我这里培养出成体系的思维方法，享受支配算法的乐趣，而不是被算法支配。