众所周知，二叉树很毒瘤
今天。本蒟蒻就van，了解一下二叉树。
首先从最基础得二叉树遍历开始
二叉树的遍历分为三种：
- 先序遍历
- 中序遍历
- 后序遍历
先序遍历和后序遍历没有什么好讲的，看看样例就会。但是中序遍历是个很毒瘤的东西。
这次我会讲解一个比较好用的小技巧。
首先给出题目（LightningUZ大佬提供）
毒瘤的二叉树遍历题目
大家仔细想一想，在纸上做一下
在这里插入图片描述
接下来给出答案：
先序：1 2 3 4 5 7 8 6 9 10 11 12 13 14 16 17 15 18
中序：3 2 7 5 8 4 9 6 11 10 12 1 16 14 17 13 15 18
后序：3 7 8 5 9 11 12 10 6 4 2 16 17 14 18 15 13 1
先序大家应该能理解，这里我就讲解一下中序和后序。
后序：这里我们就要用到一个小技巧：找最深的左儿子
例如此图：遍历根节点的左儿子时，一路遍历左儿子（不要右拐），直到到节点‘3’无法再遍历左儿子时，则输出3，这时我们直接忽略掉节点‘3’，再次回到回到节点2，遍历节点2的右儿子，再次一直遍历左儿子，直到节点7，无法再遍历，输出7，然后忽略节点7，回到节点5，遍历右儿子，我们发现遍历右儿子节点8时无法遍历任何节点了，则输出8，回到节点5，忽略节点8。因为我们已经忽略了节点7和节点8，所以我们无法在节点5继续遍历，则输出5，回到节点4，然后继续遍历右儿子，以此类推（这里建议大家图片和文字一起看，不然会有些迷糊），这里和布尔数组vis[]有异曲同工之妙。
中序遍历时最毒瘤的：和后序一样，我们仍然需要用到“找最深左儿子”的技巧，但是和它不同的是，它要多加一步：回到上一深度的节点时，直接把上一深度节点输出。
如此图：仍然时遍历到节点3时输出3，回到节点2，但此处直接输出2，然后屏蔽掉节点2（即之后不再输出2）其他的同上，比如我们遍历到了节点7，输出7，然后回到节点5，这时输出5，然后遍历8，输出8，之后直接跳过输出5（因为已经屏蔽了），之后回到4，一样，输出4，之后继续遍历，以此类推。
这是我在大佬LightningUZ的指导下摸索出来的一个小技巧（感谢！），可能有些混乱，请大家图文结合，反复观看！当你看懂了，则就掌握了！
接下来给大家出两道题目，大家可以先思考！
如果哪里不对，请善意指出（别喷啊）
欢迎各位dalao留言！
题目1
在这里插入图片描述
题目2
image
