- 先在开头总结一下，思维模式分两类：https://labuladong.github.io/algo/2/19/33/
- 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
- 2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
- 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
- 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
- 如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了
- 快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
- 先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？
- 再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。
- 先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛，不过如此呀。
- 快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
- 深入理解前中后序
- 我先甩给你几个问题，请默默思考 30 秒：
- 1、你理解的二叉树的前中后序遍历是什么，仅仅是三个顺序不同的 List 吗？
- 2、请分析，后序遍历有什么特殊之处？
- 3、请分析，为什么多叉树没有中序遍历？
- 1、你理解的二叉树的前中后序遍历是什么，仅仅是三个顺序不同的 List 吗？
- 先不管所谓前中后序，单看 traverse 函数，你说它在做什么事情？
- 数组
- 链表
- 倒序打印链表：
- 前序位置的代码在刚刚进入一个二叉树节点的时候执行；
- 后序位置的代码在将要离开一个二叉树节点的时候执行；
- 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
- 你可以发现每个节点都有「唯一」属于自己的前中后序位置，所以我说前中后序遍历是遍历二叉树过程中处理每一个节点的三个特殊时间点。
- 这里你也可以理解为什么多叉树没有中序位置，因为二叉树的每个节点只会进行唯一一次左子树切换右子树，而多叉树节点可能有很多子节点，会多次切换子树去遍历，所以多叉树节点没有「唯一」的中序遍历位置。
- 数组
- 我先甩给你几个问题，请默默思考 30 秒：
- 二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
- 二叉树最大深度：
- 遍历：
- 分解问题：
- 遍历：
- 前序遍历：
- 遍历：
- 分解：一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
- 遍历：
- 二叉树最大深度：
- 综上，遇到一道二叉树的题目时的通用思考过程是：
- 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
- 2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
- 3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。
- 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
- 后序位置的特殊之处
- 中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。
- 前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。
- 你可以发现，前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的：意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。
- 遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
- 1、如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
- 个节点在第几层，你从根节点遍历过来的过程就能顺带记录
- 个节点在第几层，你从根节点遍历过来的过程就能顺带记录
- 2、如何打印出每个节点的左右子树各有多少节点？
- 而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚。
- 而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚。
- 中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。