一.二叉树创建字符串
1）题目介绍＆oj链接
2）题目逐过程分析&完整代码
- 主要思路是通过 前序遍历 （根->左子树->右子树）方式遍历二叉树
- 我们可以利用 容器string ＆ += 追加字符【（ 】【 ）】
- 于是我们得到下面所示基本代码
- 注意点，题目的要求：转换后的结果如果右子树为空，则可以省略；如果左子树为空，右子树不为空，则不省略 ，如下图所示：
- 所以我们要在基础代码的基础上根据情况分类加上限定条件
- 可以利用上 【||】自左向右进行判断 的性质
- 分为以下三种情况（情况1＆2可以合并成一种）
1. 左子树为空，走【||】判断，右子树不为空——>打印左子树空括号
2. 左子树不为空，直接进——>打印左子树括号+节点
3.右子树不为空，直接进——>打印右子树括号+节点- （PS：由于加上了条件限制：左右均为空时，递归函数直接返回，不会打印空括号）
- 最终代码如下图所示
二.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
1）题目介绍＆oj链接
2）题目逐过程分析
- 公共祖先的特征：一个节点在我的左子树，一个节点在我的右子树，则我就是公共祖先
- 因此我们需要利用到【查找】功能（前序遍历：根—>左子树—>右子树）
- 接下来我们进一步进行程序设计：
- 首先明确传入的参数，1.树的根节点 2.节点1 3.节点2
- 先得到一种情况：根节点为节点1/节点2，直接返回公共祖先
- 之后需要对节点1和节点2是在左子树还是右子树进行 初步判断 ；设置四个参数，分别为节点在左还是在右的返回值；利用下图所示简单逻辑判断，快速得到返回值
- 开始进行递归判断；两个节点，同时在左时，则继续往左走；同时在右时，继续往右走；直到一左一右，递归结束；
3）题目完整代码
4）方法2：引入栈存储【查找路径】，暴力求解
- 将根元素入栈
- 根据前序遍历向下探测查找元素，并分别入栈
- 如果没找到元素（root为空时）return false，则跳出递归，将元素出栈（pop）
- 经过FindPath这一过程以后，stack path中存储的是该节点TreeNode的路径
- 最后分别对两个栈中存储的路径大小进行比较，大的路径挨个出栈，直到大小相同
- 同时出栈，最后返回公共祖先
5）方法2的完整代码
三.二叉树搜索树转换成排序双向链表
1）题目介绍＆oj链接
2）题目逐过程分析
- 解题关键性质：二叉搜索树 中序遍历（左子树->根->右子树） 时，返回节点的顺序是 从小到大
- 解题思路分析：
- 核心：如果我们能够通过 中序遍历 该二叉搜索树，并且将返回的节点按顺序存入vector中，最后再将相邻元素两两连接，则也可以实现双向链表
- 但是题目中要求如下所示：
- 于是我们 只能 从 调节结点指针 角度出发
- 结合上面的【核心】，我们知道要调节结点指针的指向——也就是 在中序遍历的过程中，让节点的左指针指向它的 前一个节点，右指针指向它的 下一个节点
- 但是我们最多只能通过 前后指针法 ——> 来让节点的左指针指向它的前一个节点（上图中6—>4），至于让右指针指向它的后一个节点则做不到（上图中6—>8）；
- 但是我们可以 让前一组的右指针指向节点（4—>6）
- 最后就是要找到 中序遍历 中的第一个节点head，不停地找左子树直到其为空即可
3）题目完整代码
四.根据一棵树的前序遍历与中序遍历构造二叉树
1）题目介绍＆oj链接
2）题目逐过程分析
- 这道题解题关键步骤在于： 利用 前序遍历 确定根，利用 中序遍历 分割左右区间
- 根据以上核心思路：
- 我们需要一个 整型prei 在前序遍历中确定根—— prei记得要初始化成0
- 我们需要一个 节点rooti 在中序遍历中分割区间；
- 程序设计板块:
1. （第一次进入函数时）创建与前序遍历对应的根节点
2. 利用while循环，在中序遍历中找到与 preorder[i] 对应的 节点rooti
3. 前序遍历中确定下一个根
4. 根据第2步找到的rooti， 划分左右区间 ，在左子树与右子树中进行递归操作
3）题目完整代码
4）对比同类型题目：“根据一棵树的中序遍历与后序遍历构造二叉树”
- 后序遍历和前序遍历不同点在于，其访问根的先后顺序完全颠倒
- 因此，大体思路与【根据一棵树的中序遍历与后序遍历构造二叉树】一样：
【 利用 后序遍历 确定根，利用 中序遍历 分割左右区间 】- 具体操作：
- 【我们将prei初始化成数组大小，prei–】
- 题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
五.不使用递归，利用【迭代法】实现“前序遍历”
1）题目介绍＆oj链接
2）题目逐过程分析
- 核心思路：由于题目要求采用迭代法，所以我们要引入 【栈】
- 概述：入手点应该放在 当前节点cur的变化， （1) cur一直找左子树入栈 （2) cur找到空时，会开始出栈顶元素并压入vector中 （3) cur重新指向被出的栈顶元素的右子树根节点（重复上述过程直到cur为空且栈为空）
- 程序设计板块:
1. 设置一个栈，设置一个待返回的数组vector，设置一个指针cur指向当前节点
2. 利用一个while循环，不停地取左树节点，并且 将节点压入栈中
3. 取完左路节点时（当前所在节点为空时），将栈中的元素出栈的同时把节点的值push进要返回的数组vector中，随后访问其右路 (当前节点指向其右路节点)4. 迭代法核心：用一个 while循环 嵌套 （跳出循环的条件：当前节点为空，且栈为空）
- （访问右路的过程，即是重复过程1的子问题如下图所示）
