跌跌撞撞看代码随想录看leetcode官方题解，终于写完了hot100的二叉树部分。
这是我第一次学习如何正式的用java去写一个二叉树
首先在自己的编译器里定义一个TreeNode类，以便于后面刷题的时候复用
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
第一题——二叉树的中序遍历
没什么好说的，入门题目，递归一下就有答案了。
前中后序遍历只需要记住根左右，左根右，左右根即可。
第二题——二叉树的最大深度
这道题目我使用的是后序遍历，左右根：取左右的最大层数，根的层数是最大层数+1
第三题——翻转二叉树
很明显需要先对根进行操作，调换左右子树位置，所以使用的是先序遍历。
第四题——对称二叉树
这道题在做的时候我的思路有一点错误：中序遍历左根右，乍一看示例1我们发现中序遍历是符合对称的，其实不然。
对称二叉树一定可以中序遍历对称；而中序遍历对称不一定是对称二叉树。
所以我们可以选择先补全树：只要树的左节点和右节点不同时为空，那么就把他的空节点补为null。
或者另一种做法：因为是满足对称，所以我们可以让左右子树同时递归：左子树的左节点对应右子树的右节点；左子树的右节点对应右子树的左节点。一旦只有一方为null或者两值不相等那么就判断该树不对称
关于返回值：以最简单的三层树为例：第三层不相等我们会直接返回false，这时第二层会收到左子树和右子树两个的返回结果，一旦有一个false，那么第二层也应该返回false，这样层层返回的递归思想。只要有一个false，那么往上返回的结果就都会是false
第五题——二叉树的直径
这道简单题？自己做的话我是想不出来怎么做。其实现在回头一看，他和第二道题有些相似处，可能我当时隔了太久吧
同样需要后序遍历：取左子树和右子树深度的最大值再+1，作为当前根节点的深度，除此以外我们还需要维护一个最大直径的全局变量：直径是两个节点之间的长度，从根节点来说，直径=左子树深度+右子树深度
第六题——二叉树的层序遍历
这题代码随想录的方法我记得印象很深，可能是从这里开始我就开始认真刷题了，也可能是这里开始我做二叉树开始变快了。
我们需要用到额外的数据结构来实现层序遍历：先进先出的队列
先把根节点扔进队列里，然后记录队列的长度。接下来把队列内的treeNode依次丢入数组，每出一个treeNode就意味着我们要新放入他的子节点，这样当我们把记录好的size丢到0时，保证队列里的数据是下一层（层序遍历，很奇妙吧.jpg）然后重复上述记录队列长度的操作。
第七题——将有序数组转换为二叉搜索树
这题同样是代码随想录的方法：二叉搜索树即左子树永远小于根节点，右子树永远大于根节点。
题目要求是平衡二叉搜索树（即左右子树深度差不得大于1）。因此最中间的节点肯定就是根节点，而根节点左边的数据肯定是左子树，右边的数据肯定是右子树。然后以此递归（不知道为什么让我想起了二分查找）
第八题——验证二叉搜索树
这道题已经忘记了代码随想录是怎么讲的了......
看二叉树的图的时候我想起来，这题应该用中序遍历，左根右。第七题提到了什么是二叉搜索树，那么依照左根右的遍历顺序，我们得到的list一定是依次递增的。
代码随想录给的进阶方案是：维护一个preTreeNode，他一直是当前节点的前一个节点。我们只需要判断当前节点是否大于前一个节点即可
第九题——二叉搜索树中第K小的元素
依旧是中序遍历，我们只需要额外维护一个记录当前是第几小的元素的全局变量即可，自己秒了。
第十题——二叉树的右视图
这题没读懂题啊，什么弱智能出出来这种题？？？而且给的样例和屎一样我完全不懂哇！
翻阅评论区大神，原来只需要取出二叉树最右边的所有节点即可。
层序遍历秒了，这里只留下最后一个节点存入list，其他节点通通拜拜
第十一题——二叉树展开为链表
题目有些难懂，后来知道原来只是把二叉树先序遍历的结果写成链表。不过题目中要求的是根节点还是那个根节点。
这里我的做法是先把二叉树先序遍历一下存储结果，然后再依据结果修改树：左节点置空，右节点安装遍历结果依次插入，这里要控制好遍历结果和树的对应关系：遍历结果肯定是包含根节点的，因此我们需要让根节点的右孩子指向i=1的元素
第十二题——从前序和中序遍历构造二叉树
这题就是比较难的了，毕竟我学数据结构的时候只能是靠人脑推算，现在让我写代码，两眼一闭。
再一次听代码随想录讲了数据结构的知识，其实听了一遍感觉简单了不少：
1.根据前序/后序遍历，我们可以确定谁是根节点。
2.根据根节点+中序遍历根节点的位置，我们可以确定根节点的左子树与右子树
3.根据中序遍历我们获取了左右子树之后，再回过头来看前序/后序遍历，我们就可以找到新的根节点
这里的难点是数组切分，根据根节点+中序遍历我们可以得知左子树长度和右子树长度；然后依据长度我们再去前序/后序遍历寻找子树的根节点
第十三题——路径总和III
为了做这道题我把路径总和I和路径总和II也给写了
路径总和I：这里使用的是前序遍历，从根节点出发，每经过一个节点，我们所求的数就减少当前节点的val，当到叶子节点并且所求数减到0，那么说明这条路径就是我们需要的路径
路径总和II：这道题对我来说很难，因为代码随想录没讲.....我遇到的难点是我只能存下来一个list数组，而且还是倒置的，倒置问题可以用Collections.reverse解决，存下一个数组这种拷贝问题我不会解决，
后看官方题解：不需要使用list，转为使用deque，这样就不需要解决倒置问题。每经过一个节点就把他offer进deque中，当我们递归返回的时候只需要把他poll出去即可，这样按照总和I的解决方案即可求出所有具体路径。因为要求同样是叶子节点，所以最后的判定条件是左右孩子都为空且所求数减少到0。（感觉这道题是我上一道没有完全听懂代码随想录方案导致做不出来，做完之后对回溯又有了进一步理解）
路径总和III：直接变态难，这回不规定是不是根节点，叶子节点，只要是从上往下的和为所求值即可，我直接懵逼！后看官方题解了解大意最终AC了题目：我们把所有节点都看为根节点，像总和I一样向下延伸看能否得到一个和，只要得到了一个可用值就记录。当最开始的根节点遍历结束后，我们再对他的左右子树进行同样的做法。也就是说其实这里是遍历了两次树，第一次遍历是为了找我们需要的根节点，第二次遍历才是找我们需要的总和值。
第十四题——二叉树的最近公共祖先
一个很绕的题，这题我看了别人的解法大概自己写出来了。
这题只能使用后序遍历，因为需要左右孩子的数据来推导根节点，题目中说了不会有重复的val，所以我们设置了一个状态：一旦左右孩子有一个是我们需要的节点，那么从他开始（他本身也算）都会向上返回一个标志，如果两个标志相遇了，那么他们相遇的treeNode就是他们的祖先。其实这题还耗费了我不少时间：我只考虑了左右孩子是我们需要的节点的时候向上传递标志，后面他们的父节点也要携带标志向上传递我没有实现。
第十五题——二叉树中的路径最大和
这题和路径总和系列不太像，和求二叉树的直径问题有些相似
这道题难在我们需要记录的东西比较多：路径最大和需要记录，某一节点向下延伸的最大值我们也需要记录，很绕。
我们在记录某一节点的最大值时，需要比较他的左右子树谁大，然后加到当前节点的数值，是两个操作数。是树形DP。而我们需要求的最大值，他却是三个操作数：左子树+右子树+自身，而非左子树或右子树+自身
标签：左子,遍历,中序,右子,LeetCode,hot100,二叉树,节点 From： https://www.cnblogs.com/kun1790051360/p/18449396