今天是小浩算法 “365刷题计划” 二叉树入门 - 整合篇。本篇作为入门整合篇，已经砍去难度较大的知识点，所有列出的内容，均为必须掌握。因为很长，写下目录：
二叉树是啥
二叉树的最大深度（dfs）
二叉树的层次遍历（bfs）
二叉搜索树验证
二叉搜索树查找
二叉搜索树删除
平衡二叉树
完全二叉树
二叉树的剪枝
二叉树有多重要？单就面试而言，在 leetcode 中二叉树相关的题目占据了300多道，近三分之一。同时，二叉树在整个算法板块中还起到承上启下的作用：不但是数组和链表的延伸，又可以作为图的基础。总之，非常重要！
什么是二叉树？官方是这样定义的：在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
上面那是个玩笑，二叉树长这样：
二叉树常被用于实现二叉查找树和二叉堆。树比链表稍微复杂，因为链表是线性数据结构，而树不是。树的问题很多都可以由广度优先搜索或深度优先搜索解决。
一般而言，我们会看到下面这些与树相关的术语：
小浩概念
与树相关的术语
树的结点（node）：包含一个数据元素及若干指向子树的分支；
孩子结点（child node）：结点的子树的根称为该结点的孩子；
双亲结点：b 结点是a 结点的孩子，则a结点是b 结点的双亲；
兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点
子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度：树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，比如家族树；
无序树：不考虑子树的顺序；
了解了上面的基本概念之后。我们将通过几道例题，为大家引入树的经典操作。
复习上面的概念：树的深度指的是树中最大的结点层。
第104题：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
基本概念掌握：每个节点的深度与它左右子树的深度有关，且等于其左右子树最大深度值加上 1。即：
maxdepth(root) =
max(maxdepth(root.left),maxdepth(root.right)) + 1
以 [3,9,20,null,null,15,7] 为例：
我们要对根节点的最大深度求解，就要对其左右子树的深度进行求解
我们看出。以4为根节点的子树没有左右节点，其深度为1。而以20为根节点的子树的深度，同样取决于它的左右子树深度。
对于15和7的子树，我们可以一眼看出其深度为1。
由此我们可以得到根节点的最大深度为
根据分析，我们通过递归进行求解：
其实我们上面用的递归方式，本质上是使用了dfs的思想。所以这里就可以引出什么是dfs：深度优先搜索算法（depth first search），对于二叉树而言，它沿着树的深度遍历树的节点，尽可能深的搜索树的分支，这一过程一直进行到已发现从源节点可达的所有节点为止。( 注意，这里的前提是对二叉树而言。dfs本身作为图算法的一种，在后续我会单独拉出来和回溯放一起讲。)
如上图二叉树，它的访问顺序为：
a-b-d-e-c-f-g
到这里，我们思考一个问题？虽然我们用递归的方式根据dfs的思想顺利完成了题目。但是这种方式的缺点却显而易见。因为在递归中，如果层级过深，我们很可能保存过多的临时变量，导致栈溢出。这也是为什么我们一般不在后台代码中使用递归的原因。如果不理解，下面我们详细说明：
事实上，函数调用的参数是通过栈空间来传递的，在调用过程中会占用线程的栈资源。而递归调用，只有走到最后的结束点后函数才能依次退出，而未到达最后的结束点之前，占用的栈空间一直没有释放，如果递归调用次数过多，就可能导致占用的栈资源超过线程的最大值，从而导致栈溢出，导致程序的异常退出。
所以，我们引出下面的话题：如何将递归的代码转化成非递归的形式。这里请记住，基本所有的递归转非递归，都可以通过栈来进行实现。非递归的dfs，代码如下：
上面的代码，唯一需要强调的是，为什么需要先右后左压入数据？是因为我们需要将先访问的数据，后压入栈（请思考栈的特点）。
如果不理解代码，请看下图：
说明：
1：首先将a压入栈
2：a弹栈，将c、b压入栈（注意顺序）
3：b弹栈，将e、d压入栈
4,5：d、e、c弹栈，将g、f压入栈
6：f、g弹栈
至此，非递归的 dfs 就讲解完毕了。那如何通过非递归dfs的方式，来对本题求解呢？相信已经很简单了，这个下去自己试试就ok了了。
在上文中，我们通过例题学习了二叉树的dfs（深度优先搜索），其实就是沿着一个方向一直向下遍历。那我们可不可以按照高度一层一层的访问树中的数据呢？当然可以，就是本节中我们要讲的bfs（宽度优先搜索），同时也被称为广度优先搜索。
第102题：给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
/ \
9 20
15 7
返回其层次遍历结果：[[3],[9,20],[15,7]]
bfs，广度/宽度优先。说白了就是从上到下，先把每一层遍历完之后再遍历一下一层。假如我们的树如下：
按照bfs，访问顺序如下：
a->b->c->d->e->f->g
了解了bfs，我们开始对本题进行分析。同样，我们先考虑本题的递归解法。想到递归，我们一般先想到dfs。我们可以对该二叉树进行先序遍历（根左右的顺序），同时，记录节点所在的层次level，并且对每一层都定义一个数组，然后将访问到的节点值放入对应层的数组中。
假设给定二叉树为[3,9,20,null,null,15,7]，图解如下：
根据分析，代码如下：
上面的解法，其实相当于是用dfs的方法实现了二叉树的bfs。那我们能不能直接使用bfs的方式进行解题呢？当然可以。我们使用queue的数据结构。我们将root节点初始化进队列，通过消耗尾部，插入头部的方式来完成bfs。
具体步骤如下图：
根据分析，完成代码：
bst是二叉搜索树，很重要。bst是二叉搜索树，很重要。bst是二叉搜索树，很重要。重要的事情说三遍。
第98题：给定一个二叉树，判断其是否是一个有效的二叉搜索树。
示例 1:
输入:
1 4
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
要验证二叉搜索树，首先得知道啥是二叉搜索树。二叉搜索树（binary search tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
这里强调一下子树的概念：设t是有根树，a是t中的一个顶点，由a以及a的所有后裔（后代）导出的子图称为有向树t的子树。具体来说，子树就是树的其中一个节点以及其下面的所有的节点所构成的树。比如下面这就是一颗二叉搜索树：
下面这两个都不是：
图中4节点位置的数值应该大于根节点
图中3节点位置的数值应该大于根节点
回到题目，那我们如何来验证一颗二叉搜索树？首先看完题目，我们很容易想到 遍历整棵树，比较所有节点，通过 左节点值<节点值，右节点值＞节点值 的方式来进行求解。但是这种解法是错误的，因为对于任意一个节点，我们不光需要左节点值小于该节点，并且左子树上的所有节点值都需要小于该节点。（右节点一致）所以我们在此引入上界与下界，用以保存之前的节点中出现的最大值与最小值。
代码其实很简单：
难就难在，可能大家看不懂这个递归！没事，祭出大杀器：
这里需要强调的是，在每次递归中，我们除了进行左右节点的校验，还需要与上下界进行判断。其余的就很简单了。
在上文中，我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢？
第700题：给定二叉搜索树（bst）的根节点和一个值。你需要在bst中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 null。
例如，给定二叉搜索树:
搜索: 2
你应该返回如下子树:
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 null。
先复习一下，二叉搜索树（bst）的特性：
1.若它的左子树不为空，则所有左子树上的值均小于其根节点的值
2.若它的右子树不为空，则所有右子树上的值均大于其根节点得值
3.它的左右子树也分别为二叉搜索树
如下图就是一棵典型的bst：
现在我们来看题，假设目标值为 val。根据bst的特性，我们可以很容易想到查找过程（上面的验证比查找稍难一点）：
如果val小于当前结点的值，转向其左子树继续搜索；
如果val大于当前结点的值，转向其右子树继续搜索；
如果已找到，则返回当前结点。
很简单，不是吗？然后我们可以给出迭代和递归两种解法（给个java的吧！）：
查找有了，下面自然就要讲删除。（为啥说我要着重墨在bst上面，因为bst这两年在面试时非常高频。面试官不可能说问你一个普通二叉树的题目，要么就是问堆，要么就是问bst，或者就直接dfs考察回溯。）
第450题：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
说明：要求算法时间复杂度为 o(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
2 6
\ \
如果你看到了这里，相信肯定知道bst是个啥了。所以直接分析题目。我们要删除bst的一个节点，首先需要找到该节点。而找到之后，会出现三种情况。
待删除的节点左子树为空，让待删除节点的右子树替代自己。
待删除的节点右子树为空，让待删除节点的左子树替代自己。
如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点（前驱），来替换自己
或者比当前节点大的最小节点（后继），来替换自己。
分析完毕，直接上代码。这里我们给出通过后继节点来替代自己的方案（可以自行实现另一种方案）：
bst讲解完了。上面也说了，别人考察我们肯定是考察特殊的。那二叉树里还有啥特殊的东东嘞？平衡二叉树算是一个。
**第110题：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：**
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
3 3
4 4
返回 false 。
题其实是一道很简单的题，主要是拿来复习一下高度。我们想判断一棵树是否满足平衡二叉树，无非就是判断当前结点的两个孩子是否满足平衡，同时两个孩子的高度差是否超过1。那只要我们可以得到高度，再基于高度进行判断即可。
这里唯一要注意的是，当我们判定其中任意一个节点如果不满足平衡二叉树时，那说明整棵树已经不是一颗平衡二叉树，我们可以对其进行阻断，不需要继续递归下去。
然后还有一个初学者容易懵逼的：
这玩意，并不是平衡二叉树。上代码：
还有啥特殊的，要捞出来讲一讲的？
第222题：给出一个完全二叉树，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
2 3
/ \ /
4 5 6
输出: 6
老样子，我们得说说啥是完全二叉树。完全二叉树由满二叉树引出，先来了解一下什么是满二叉树。如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。（二叉树的度代表某个结点的孩子或者说直接后继的个数，这个在上面已经说过了。对于二叉树而言，1度是只有一个孩子或者说单子树，2度是有两个孩子或者说左右子树都有。）
那什么又是完全二叉树呢：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。比如下面这颗：
这个就不是：
上面做了这么多题了，你应该能想到我要说啥 --- 递归。二叉树的题目基本上都可以递归求解。
但是很明显，出题者肯定不是要这种答案。因为这种答案和完全二叉树一毛钱关系都没有。所以我们继续思考。
由于题中已经告诉我们这是一颗完全二叉树，我们又已知了完全二叉树除了最后一层，其他层都是满的，并且最后一层的节点全部靠向了左边。那我们可以想到，可以将该完全二叉树可以分割成若干满二叉树和完全二叉树，满二叉树直接根据层高h计算出节点为2^h-1，然后继续计算子树中完全二叉树节点。那如何分割成若干满二叉树和完全二叉树呢？对任意一个子树，遍历其左子树层高left，右子树层高right，相等左子树则是满二叉树，否则右子树是满二叉树。这里可能不容易理解，我们看图。
假如我们有树如下：
我们看到根节点的左右子树高度都为3，那么说明左子树是一颗满二叉树。因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是2^left - 1，加上当前这个root节点，则正好是2^3，即 8。然后只需要再对右子树进行递归统计即可。
那假如我们的树是这样：
我们看到左子树高度为3，右子树高度为2。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为2^right，即2^2。再对左子树进行递归查找。
根据分析，得出代码：
该讲的都讲了，突然想到忘了一个经典操作 - 剪枝。迅速补上！非常重要！这里额外说一点，就本人而言，对这个操作以及其衍化形式的使用会比较频繁。因为我是做反欺诈的，机器学习里有一个概念叫做决策树，那如果一颗决策树完全生长，就会带来比较大的过拟合问题。因为完全生长的决策树，每个节点只会包含一个样本。所以我们就需要对决策树进行剪枝操作，来提升整个决策模型的泛化能力... 听不懂也没关系，简单点讲，就是我觉得这个很重要，或者每道算法题都很重要。如果你在工作中没有用到，不是说明算法不重要，而可能是你还不够重要。
第814题：给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。
( 节点 x 的子树为 x 本身，以及所有 x 的后代。)
示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。
示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
说明:
给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。
还是先解释一下，啥是剪枝：假设有一棵树，最上层的是root节点，而父节点会依赖子节点。如果现在有一些节点已经标记为无效，我们要删除这些无效节点。如果无效节点的依赖的节点还有效，那么不应该删除，如果无效节点和它的子节点都无效，则可以删除。剪掉这些节点的过程，称为剪枝，目的是用来处理二叉树模型中的依赖问题。
说了好多遍了，二叉树的问题，大多都可以通过递归进行求解。直接分析。假设我们有二叉树如下：[0,1,0,1,0,0,0,0,1,1,0,1,0]：
长这样：
剪枝之后是这样：
剪什么大家应该都能理解。那关键是怎么剪？过程也很简单，在递归的过程中，如果当前结点的左右节点皆为空，且当前结点为0，我们就将当前节点剪掉即可。
其实很简单，直接看代码：
二叉树入门整合系列篇到这里就完事了，相信大家如果可以完整看完，一定会有所收获。但是呢，其实大家可以看到，上面的系列还有很多内容没有讲。比如很核心的一块dfs和回溯。这些都会在后面出单独的系列进行讲解，希望大家多多支持！
今天的整合篇去除了之前的一些冗余内容，对部分图解也进行了重构，熬夜整合，猝死边缘。