【C++二叉树】二叉树的前序遍历、中序遍历、后序遍历递归与非递归实现
1.二叉树的前序遍历
144. 二叉树的前序遍历 - 力扣（LeetCode）
前序遍历方式：根-左子树-右子树。
递归实现：
要传一个子函数来实先递归，原因是原函数返回值为vector，在原函数迭代，返回值就难处理了。
非递归（迭代）实现：
递归实现非常简单，非递归呢？
要用迭代实现，也就是循环：
还是按照根-左子树-右子树的遍历方式遍历。
遍历：先访问1、3、4再访问4的右子树再退回去访问3的右子树和1的右子树。
这时，我们可以把树分为左路节点和左路节点的右子树。
也就是先访问左路节点再访问左路节点的右子树，右子树也同样分为左路节点和左路节点的右子树。
这时，就要使用栈来解决：
- 把左路节点入栈，入栈的同时访问节点（遍历根），当左路节点为空时停止入栈，同时也证明左子树已经访问结束。
- 这时再访问左路节点的右子树。取栈顶数据（栈顶数据就是左路节点）的右子树，再把栈顶数据弹出。
- 右子树同样分为左路节点和左路节点的右子树，同样按照此方法迭代循环。
- 直到最后一个节点访问结束，此时，节点为空，栈为空。
自己根据代码，画一下图模拟迭代过程就容易理解了。
2.二叉树的中序遍历
94. 二叉树的中序遍历 - 力扣（LeetCode）
中序遍历方式：左子树-根-右子树。
递归实现：
非递归（迭代）实现：
中序遍历的非递归和前序遍历的非递归思路类似。
- 都是按照把树分为左路节点和左路节点的右子树的思路来实现的，只不过访问节点（根）的时机不同。
- 前序遍历是先访问根再访问左子树右子树，所以在左路节点入栈的时候，就访问节点（根），而中序遍历是先访问左子树再访问根再访问右子树
- 所以中序遍历是在左路节点入栈完以后，再访问节点（根）。
3.二叉树的后序遍历
145. 二叉树的后序遍历 - 力扣（LeetCode）
后序遍历方式：左子树-右子树-根
递归实现：
非递归迭代实现：
后序遍历方式：左子树-右子树-根
后序遍历的非递归与前序和中序的非递归整体思路类似。
唯一不同的就是访问节点的时机不同。
什么时候访问节点（根）呢？
- 从栈中取出左路节点时，节点的左子树已经访问完了（理解理解）。
- 当左路节点的右子树访问完才可以访问根。
- 如果左路节点的右子树为空，则代表右子树访问完，可以访问节点（根）了。
- 如果右子树不为空，则要先访问左路节点的右子树。
非递归迭代实现：
但是此时会发现超出了内存限制，说明代码有问题，内存限制问题一般就是死循环了。
按照上面的代码，会发现，节点3和节点5之间会一直死循环，
- 3的右子树不为空，把5入栈，5的右子树为空，把栈中5弹出来，下次循环又取了栈顶数据3，3的右子树不为空，把5入栈......
- 第二次访问节点3的时候，就应该直接访问节点（根）了，但他的右子树不为空，又访问了右子树，他不知道右子树已经访问过了，就会不断的进入3的右子树访问就死循环了。
所以，关键问题就说我们要想一个办法区分他的右子树到底访问过了没有，如果访问过了，则可以访问该左路节点（根）了，如果没有访问，则先访问他的右子树。
此时，可以使用双指针来解决，我们定义一个指针lastNode表示当前节点的上一个节点。
访问节点3的时候，lastNode为右子树的根（节点5），代表右子树已经访问完了，则就可以访问该节点了。
非递归（迭代）实现：
4.总结：
- 前序遍历、中序遍历、后序遍历的递归实现很简单，但是非递归迭代实现就有稍微有点难理解了。
- 用了同一种思路，把树分为左路节点和左路节点的右子树，针对这三种遍历方式都适用。
- 从根本上就是用循环模拟递归的过程。
- 后序遍历相对前序和中序又稍微复杂，要考虑好访问节点的条件，避免死循环。
- 多画图模拟迭代的过程更容易理解。