前情回顾
对二叉树的遍历还不了解的，先去看看：二叉树的遍历 → 不用递归，还能遍历吗
简单来说，深度遍历用 栈 辅助实现，广度遍历用 队列 辅助实现
不管是递归（系统栈）实现，还是 栈 迭代 实现，深度遍历的额外空间复杂度都是：O(n)
那有没有额外空间复杂度 O(1) 的方法来实现二叉树的深度遍历呢？（O(1) 是指常数级别，而非字面 1 的意思）
还真有：morris traversal，只是遍历过程会破坏二叉树的结构，所以存在恢复二叉树结构的过程，具体实现可查看：Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）
不是很好理解，大家结合二叉树样本结构，去逐行 debug 代码，看看二叉树的遍历、结构变化，慢慢的就有感觉了
实战案例
当我们对二叉树的遍历有了一定的了解之后，我们就可以尝试解决一些二叉树的问题了
最大宽度
从根节点开始，一层一层往下统计，最大宽度即是节点数最多的那一（些）层的节点数量，例如
最大宽度就是 3
很明显，这是一个宽度（广度）遍历，那就需要用到 队列 来辅助实现
光实现宽度遍历还不够，还需要统计每一层的节点数，然后找出最大宽度；那如何统计每一层的节点数？
我们可以先用哈希表记录每个节点所处的层次，实现如下
相信大家都能看懂这个代码，就是在宽度遍历的基础上，对每个节点进行层次标记
标记完之后，再遍历 levelMap ，完成层次的个数统计？
我们知道哈希表一般是无序的，再遍历 levelMap 进行层次的个数统计，并没那么简单；非要较劲，也是可以实现的，但没比较
宽度遍历本身就是逐层进行的，当进行到下一层时，上一层肯定全部遍历完了，所以当遍历下一层的时候，上一层的节点数就应该统计出来
我们来看完整代码
简单点来说，就是在宽度遍历的基础上加入了统计的逻辑，所以重点是宽度遍历
只要能够理解宽度遍历，上述代码就很容易理解
我们再延伸下，如果不用哈希表，还能实现吗？
哈希表的作用看似是记录每个节点所在的层次，实际就是用来判断当前层次是否处理完，基于此我们可以改造下
用两个节点变量（ curEnd 、 nextEnd ）分别记录当前层的最后一个节点和下一层的最后一个节点；遍历当前层的时候，移动 nextEnd
当遍历完当前层节点（ cur == curEnd ）， nextEnd 刚好来到来到下一层的最后一个节点，将 nextEnd 赋值给 curEnd （ curEnd = nextEnd; ），开始下一层的遍历与统计
如此反复，找到最大宽度；代码如下
是不是很有意思？
我们再来延伸下，找出最大宽度的同时，找出最大宽度所在的层（可能多层），该如何实现？
这个就交给你们自己去实现了
路径总和
LeeCode 113
给定二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径（叶子节点 是指没有子节点的节点）
示例：
先序遍历，找出所有路径，过滤出路径上节点之和等于 targetSum 的路径
比较简单，直接看代码
有两个注意点：1、为什么不直接将 curPath 添加到 allPath，而是 copy 一份之后将新的添加到 allPath；2、为什么要回溯
第 1 点，正是由于回溯，导致 curPath 中的元素会变化，如果 allPath 直接添加 curPath（allPath.add(curPath)），那么 allPath 中的元素也会随着递归的出栈而变化
所以这两个注意点可以归纳为一点：为什么要回溯
不理解为什么要回溯的小伙伴，可以先去查查回溯的相关资料
在这里，回溯的作用是还原现场，保证我们能够正确的找到所有路径
折纸问题
把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开，此时有 1 条折痕，突起的方向指向纸条的背⾯，这条折痕叫做“凹”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“凸”折痕
如果每次都从下边向上方对折，对折 N 次，请从上到下打印出所有折痕的方向
我们用纸条去实操下，就会发现规律，这就是一个二叉树的中序遍历（严格来时，是满二叉树的中序遍历）
很简单，直接看代码
这题很容易，只要你去实操折纸，找到了规律，代码实现就是手到擒来
最低公共祖先
求同一棵二叉树中两个节点的最低公共祖先节点
什么是最低公共祖先，节点往上向根节点移动，两个节点最先汇聚的节点则是这两个节点的最低公共祖先，例如
10 和 4 的最低公共祖先就是 3
简单的做法是借助哈希表
先遍历一次二叉树，记录所有节点的父节点（HashMap），然后找出其中某个节点（n1）的所有祖先节点（存放到 HashSet 中）
再从另一个节点（n2）开始，从 HashMap 中逐个找 n2 的祖先节点的同时，判断 n2 的当前祖先节点是否在 HashSet 中
一旦找到，这直接返回该节点，就是 n1 与 n2 的最低公共祖先
我们来看代码
很好理解，也很好实现，就是有点费空间
还有一种方式，实现非常简单，但却不好理解，是前辈们反复提炼之后得到的一种解法
大家千万不要只盯着代码看，需要结合具体的二叉树结构、n1与n2的关系，逐行代码去模拟，去找感觉，来理解这种方式
这可是前辈们反复提炼之后的方法，如果你一眼就看懂了，那岂不是太过分了？
总结
1、二叉树的遍历是解二叉树题的基础，基础一定要打牢
相信大家已从上述几个案例中感觉到了
基础不牢，地动山摇，你们懂的
2、举的案例有限，目的也仅仅只是给大家找找感觉
有了一定的感觉，就可以力扣走起：二叉树
