二叉树解题整体框架：

        1、确定当前题型是做高度还是深度还是搜索树还是其他

                高度（从下往上，求根深度、高度等）：

                        使用后序遍历会更加简单，递归方法一般需要返回值返回上级，让上级对返回值进行判断处理;

                深度（从上往下，路径问题等）

                        使用前序遍历会更加简单，递归方法一般需要与回溯一起使用，但是在递归的结束阶段可能需要额外的判断内容（在单层逻辑左右子节点递归完需要进行回溯处理,同时在此处判断是不是存在子节点）

                搜索树

                        搜索树通过中序遍历可以变成一个从小到大的数组

                其他

                        按照递归思路解题即可

        2、使用递归的思路：

                （1）确定递归的返回值、输入值（返回值的类型，输入值的类型可以边做边添加）

                （2）确定递归的停止逻辑（当节点走到哪里就该返回或者停止）

                （3）确定递归的单层逻辑（根据前中后序或者层序遍历）

        3、使用迭代的思路：

                （1）如果题型可以使用一个队列将其左或右节点输入，然后进行队头元素的输出 就可以使用迭代的思想

        4、使用前序遍历+回溯的思路（需要注意3点）：

                一般是从上往下，需要注意以下问题：

                （1）递归返回值、输入值：

                        一般前序遍历是没有返回值，使用全局变量进行记录，如果需要返回值（true or false）需要在停止条件处进行返回对应的返回值，在单层逻辑的时候，仍旧按照先记录当前节点，使用变量获取左右递归的返回值，最后再根据返回值判断当前节点的返回值

                        输入值一般需要是引用，因为要回溯

                （2）递归的停止、判断条件

                        前序遍历的递归停止条件一般是当前节点是不是叶子节点，与后序遍历（当前节点是不是空节点不同）

                        前序遍历的返回条件无法判断根节点是不是空节点：需要在主函数中进行额外的判断

                        前序遍历的返回条件无法判断一个节点是不是空节点：需要在单层递归条件中额外的判断当前节点存在左子节点才进行左子节点的递归，存在右子节点才进行右子节点的递归，避免出现一个节点有一个空的子节点一个不空的子节点-->寻找空节点的子节点导致报错

         5、二叉搜索树的思路

                （1）对二叉搜索树中序遍历是一个有序的数组（实在做不出可以使用）

                （2）对二叉搜索树中序遍历

                        要注意：中序遍历是无法找到上一个节点位置的，所以需要建立一个全局节点去记录上一个节点（包括了二叉搜索树变成累加树中的逆中序）

                （3）要知道二叉搜索树的性质，可以达到从上往下按照已知的路径遍历，无需将所有路径进行遍历，通过返回新的当前节点来更新整棵二叉搜索树。

                

---

---

一、二叉树基础（算法11天）：

        1、二叉树的定义

        2、根节点、子节点、叶子节点、度、节点深度、高度、层、子树

        3、二叉树性质（4条）

        4、满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树（AVL）

        5、二叉树的存储方式

                链式存储是使用指针指向左右子节点

                顺序存储的子节点位置

二、二叉树的遍历方式（算法11天）

        1、深度优先

                前序（递归、迭代）中左右-->适合从上往下，深度，可能结合回溯，在递归的终止需要额外判断；迭代使用栈，根据栈的先进后出，需要先输入右节点再输入左节点

                中序（递归、迭代）左中右-->适合二叉搜索树

                后序（递归、迭代）左右中-->适合从下往上，高度，递归一般需要返回值；迭代就是前序遍历中右左之后reverse

        2、广度优先

                递归（需要加深度depth）

                迭代（必须掌握，队列）

三、二叉树题型

        1、翻转二叉树（算法12天）

                前序、后序(递归迭代都行)层序遍历（递归迭代都行）重点是使用swap交换两个子节点

        2、对称二叉树（算法12天）

               递归：

                        递归重点在于理解需要同时处理左右两个子节点的对称位置，从下到上判断是否对称-->需要返回值，类似于后序遍历，先处理左右，再处理中（要注意停止、返回条件）

                迭代：

                        使用队列记录两个节点，但是同时判断两个节点的状态。

        3、二叉树的最大深度（算法12天）

                递归（迭代）：深度是从上往下，属于是前序遍历（前序+回溯），但是最大深度，就相当于求高度，可以使用后序遍历更简单（左右中-->通过返回值记录最大深度）

        4、二叉树的最小深度（算法12天）

                递归：与最大深度类似，但是不同。

                        重点在于：深度是当前节点到叶子节点的距离（最小深度是找到最近的叶子节点，当单边是nullptr，另一边不是nullptr时，不是叶子节点，不能从当前节点到nullptr，而是到另外有子节点的边）        

                迭代：

                        同样使用队列（层序遍历）使用int depth记录深度，当前节点没有子节点就返回深度，有子节点就继续向队列中添加元素。

        5、平衡二叉树（算法13天）

                题重点：平衡二叉树就是左右子树高度最多相差1

                递归：

                        高度题：使用后序遍历-->左右中，返回值是高度，递归左右，在中判断左右的值：使用一个标志位-1表示高度差超过了1，有-1返回-1，没-1返回最大的高度

        6、二叉树所有的路径（算法13天）

                递归：

                        路径问题：从上往下开始遍历：前序遍历+回溯。

                        难点：

                                （1）注意前序遍历一般没有返回值，是在停止条件处写入全局变量

                                （2）将int转换成string:to_string()

                                （3）将string转换成int:stoi()

                        错点：因为要进行回溯：说明要传入的参数是引用而不是复制一个副本！！！！

        7、左叶子之和（算法13天）

                递归：后序遍历

                难点：理解左叶子：当前节点的左子节点的左右子节点为空

        8、二叉树左下角的值（算法14天）

                难点：

                        理解左下角：最深层 的第一个

                层序遍历简单:

                        只需要获取每一次迭代的队列中的队头元素

                递归：

                        使用前序遍历+回溯，记录vector中最大的路径长度（深度）

        9、二叉树路径总和，存在目标值（算法14天）

                前序遍历+回溯的应用

                注意点：

                        前序遍历也可以有返回值，返回值是在当前节点设置完后，对左右子节点递归获得的，之后再根据返回值设置当前节点的返回

                        因为前序遍历，停止条件为当前节点为叶子节点，没有讨论当前根节点为空，所以要注意root==nullptr的情况；没有讨论当前节点的子节点一个为空一个不空的情况，所以需要再单层递归逻辑中额外判断是否存在子节点。

        10、二叉树路径总和，全部路径（算法14天）

                前序遍历+回溯，不需要返回值了，统一记录即可

        11、从中序遍历与后序遍历构建二叉树(算法14天)

                理解：中序遍历、后序遍历的意义

                        后序遍历：左右中，说明数组最后的是中点

                        中序遍历：左中右，可以找到左数组、右数组

                递归：构建二叉树（从上往下）-->前序遍历，需要返回值-->返回值是当前节点的左子树、右子树

                难点：如何将vector数组划分成两份：

                        vector<int>left(.begin(),.begin()+i);

                        使用一个新定义的vector数组去获取原来的数组的一部分

        12、最大二叉树（算法15天）

                （类似于11题）递归：前序遍历、返回值是子树。

        13、合并二叉树（算法15天）

                同时递归两个二叉树，属于构造二叉树问题-->从上往下前序遍历，

                1、返回值是子树，输入值是两个二叉树节点：

                2、停止条件：双方都为空返回nullptr、有一方为空返回另一方

                3、单层递归逻辑：构造新节点，将两个二叉树的值添加到新节点中，递归两棵二叉树的左右子节点作为左右子树。

        14、二叉搜索树中的搜索（算法15天）

                性质：二叉搜索树左子树都比当前节点小，右子树都比当前节点大、

        15、验证二叉搜索树（算法15天）

                错误：前序遍历比较当前值与子节点的大小，返回值true or false，无法保证左子树所有元素都比右子树的元素小

                要使用中序遍历：将二叉搜索树变成一个数组，或者直接使用中序遍历进行遍历判断大小（但是因为中序遍历过程并不按照树的结构从上到下或者从下到上，所以需要一个值去记录上一个值的大小）

        16、二叉搜索树的最小绝对差（算法16天）

                思路1：中序遍历变成数组，遍历数组找到最小值       

                思路2：在中序遍历中去比较获得最小值

                重点：中序遍历需要使用一个全局节点去记录上一个节点的信息。 

        17、二叉搜索树中的众数（算法16天）

                仍旧是利用二叉搜索树的性质：中序遍历从小到大：

                数组、直接在中序遍历中操作

                重点：需要考虑有多个众数的情况：众数使用vector数组保存

        18、二叉搜索树的最近公共祖先（算法16天）

                理解：最近公共祖先：两个节点可能有一个是祖先、两个节点都不是祖先

                使用后序遍历：通过递归左右字节点去获取左右子树的返回值；停止条件：当到空节点、找到一个p或者q     

        19、二叉搜索树的最近公共祖先（算法17天）

                与18题不同，这个是针对二叉搜索树的性质进行寻找

                返回值：返回公共祖先

                从上往下遍历，当前节点的值在两个值之间说明当前节点就是最近公共祖先

                当前节点的值在大于两个值，说明需要向左子树遍历，返回左子树的值

                当前节点的值在小于两个值，说明需要向右子树遍历，返回右子树的值

        20、二叉搜索树中的插入操作（算法17天）

                理解插入的本质：最简单的插入是不破坏二叉搜索树的结构，在合适的节点的子节点（空节点）插入需要插入的值

                返回值：可以是当前值（由nullptr-->val）

        21、删除二叉搜索树中的节点（算法17天）

                理解删除的本质以及后果：

                        通过二叉搜索树的性质从上往下找到要删除的节点，判断节点的类型：

                        （1）空，返回空

                        （2）叶子，返回空

                        （3）子节点一个有值，一个空，返回有值子树

                        （4）子节点全部有值，将右子树接上，左子树放到右子树的最左下位置

        22、修剪二叉搜索树（算法18天）

                理解修剪的定义：

                        找到一个范围，使得二叉搜索树中所有值都在这个范围中，不改变树的整体结构（无法使用中序变数组、数组减枝、数组变二叉搜索树）

                通过二叉搜索树的性质，向下进行递归，判断

                        （1）当前节点<最小值：说明当前节点以及左子树全部去掉，对右子树进行查找有没有符合区间的值，返回的是符合区间的值（更新后的当前节点的值）

                        （2）当前节点>最大值：说明当前节点以及右子树全部去掉，对左子树进行查找有没有符合区间的值，返回的是符合区间的值（更新后的当前节点的值）

                        （3）当前节点在区间内，对左右子节点进行递归，去除不符合的节点，返回当前更新后的节点。

        23、有序数组转化为二叉搜索树（算法18天）

                        数组二分法

        24、二叉搜索树转换为累加树（算法18天）

                理解累加树：

                        当前节点的值+所有比当前节点值大的值

                逆中序遍历：

                        将当前值与前一个值进行相加，所以需要一个全局变量去记录前一个值