原文链接：https://labuladong.gitee.io/algo/1/7/
我刷了这么多年题，浓缩出二叉树算法的一个总纲放在这里，也许用词不是特别专业化，但目前各个刷题平台的题库，没有一道二叉树题目能跳出本文划定的框架。如果你能发现一道题目和本文给出的框架不兼容，请留言告知我。
先在开头总结一下，二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
本文中会用题目来举例，但都是最最简单的题目，所以不用担心自己看不懂，我可以帮你从最简单的问题中提炼出所有二叉树题目的共性，并将二叉树中蕴含的思维进行升华，反手用到 动态规划， 回溯算法， 分治算法，图论算法 中去，这也是我一直强调框架思维的原因。
首先，我还是要不厌其烦地强调一下二叉树这种数据结构及相关算法的重要性。
举个例子，比如两个经典排序算法 快速排序 和 归并排序，对于它俩，你有什么理解？
如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了。
为什么快速排序和归并排序能和二叉树扯上关系？我们来简单分析一下他们的算法思想和代码框架：
快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1]和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
快速排序的代码框架如下：
**void** sort(**int**[] nums, **int** lo, **int** hi) {
*/****** 前序遍历位置 ******/// 通过交换元素构建分界点 p*
**int** p = partition(nums, lo, hi);
*/************************/*
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？
再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。
归并排序的代码框架如下：