我们都知道，二叉树常见的操作之一就是遍历，leetcode上很多对二叉树的操作都是基于遍历基础之上的。
二叉树的遍历操作分为深度优先遍历和广度优先遍历，深度优先遍历包括前序、中序、后序三种遍历方式；广度优先遍历又叫层序遍历。
这两种遍历方式都是非常重要的，树的层序遍历一般是没法通过递归来实现，其遍历过程需要借助一个队列来实现，本质上就是图的BFS的一种特例，可以用来求二叉树的高度、宽度等信息。
我们今天要讲的是二叉树的前、中、后序遍历的非递归算法。
二叉树前、中、后序遍历的递归算法形式上上是非常简洁明了的，只要你熟练使用递归这一方法，应该都能写出来。
而非递归算法则显得不那么容易。但是非递归算法也非常重要，有一些题用非递归算法解会简单一点。
其实，我觉得我们人类的思维就是典型的非递归形式的，所以，要想实现一个非递归算法，其实就是把我们脑中的求解过程转换成相应的代码。
前序非递归
例如，对于下面这棵二叉树，我们要对其进行非递归前序遍历，该如何做？
前序遍历，就是先访问根节点，再访问左子树，再访问右子树，左子树和右子树的访问过程也是这样递归进行。
那么我们一开始是依次访问1、2、4、6。到了6的时候我们为什么要停下来呢？因为这时候我们发现，6的左子树为空，相当于它的左子树已经访问完了，按照前序遍历的定义，这个时候我们应该访问其右子树，我们发现6的右子树也为空，相当于它的右子树访问完了。
这个时候我们该怎么办呢？
没错，这个时候说明以6为根节点的子树都已经访问完了，我们应该往上回溯，回到6的父亲结点。
从这里，我们发现了几个问题：
- 我们每个结点都要经过3次
- 第一次是从该结点的根结点往下走到该结点的时候经过的
- 第二次是从其左子树返回到该结点时经过的
- 第三次是从其右子树返回到该结点时经过的。
- 前序遍历一开始是不断地往左下角方向走，每经过一个结点就访问它，直到到达最左下角位置停下来。
- 每当从左孩子返回到根结点的时候，需要判断一下右子树是不是为空，不为空的话才去访问右子树。
- 由于存在回溯，所以访问过程需要用到栈，用来记录我们依次经过的结点。
初步思考之后，我们可以写出如下代码：
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root;
if (p) {
res.push_back(p->val);
s.push(p);
}
while (!s.empty()) {
p = s.top();
while (p->left) {
res.push_back(p->left->val);
s.push(p->left);
p = p->left;
}
if (p->right) {
res.push_back(p->right->val);
s.push(p->right);
p = p->right;
}
else {
p = s.top(); s.pop();
}
}
return res;
}
res数组是用来记录我们访问序列的，p指向我们当前经过的结点，s用来记录我们走过的结点序列。
这个代码乍一看好像和我们刚才思考的过程是一样的，但是你一运行就会出现问题，首先，我们来看一下这个循环
p = s.top();
while (p->left) {
res.push_back(p->left->val);
s.push(p->left);
p = p->left;
}
我们上面讲过，二叉树中每个结点都会经过三次，我们这里一直在往左下角方向走，每走一步记录一个结点到栈里面，并且访问该结点。
但是，你有没有发现，还是针对我们之前那棵树：
当我们访问完6回到4的时候，这个循环条件同样又成立了，它又会重复一次往左下角走，这并不是我们想要的，那么怎么办？
你可以想一下，这种情况是什么条件才会触发的？
没错，就是我们刚从左子树返回的时候，言外之意就是说，我们上一个访问的结点是左孩子。所以为了避免这种情况发生，我们必须记录一下上一个访问过的结点是什么？
为此我们新加一个pre指针，指向上一个访问过的结点，这个结点需要我们每走一步都更新一次。
同时我们会发现，当我们从右子树返回的时候，我们也不能进入上面那个循环。
比如对于之前那个图，当我们从7返回到4的时候，我们不应该再次往4的左孩子方向走。
还有一个类似的问题，就是我们往右孩子方向走不仅仅需要右孩子非空，而且需要保证上一个访问过的结点不是右孩子。
于是，引入这个pre指针之后，我们之前的代码可以改成下面这样的
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root, * pre = p;
if (p) {
res.push_back(p->val);
s.push(p);
}
while (!s.empty()) {
p = s.top();
while (p->left && p->left != pre && p->right != pre) {//没有从左边返回，也没有从右边返回
res.push_back(p->left->val);
s.push(p->left);
pre = p;
p = p->left;
}
if (p->right && p->right != pre) {
res.push_back(p->right->val);
s.push(p->right);
pre = p;
p = p->right;
}
else {
pre = s.top();
s.pop();
}
}
return res;
}
这次我们的代码终于没有任何问题了。
讲完二叉树的前序非递归算法，我们再讲讲中序和后序非递归算法。其实理解了前序，我们只需要做一些微小的修改就行，整体过程还是类似的。
中序非递归
还是以我们上面那棵树为例，我们来讲讲中序遍历过程
中序遍历，就是先访问左子树，再访问根节点，最后访问右子树，左子树和右子树的访问过程也是这样递归进行。
那么我们一开始访问的是哪个元素呢？
没错，由于我们先是对左子树进行递归，所以我们一开始访问的应该是最左下角位置的元素
这个和前序是有一点区别的，前序是往左下角方向走，每走一步访问一个结点。中序是先一下子走到左下角，然后再访问最左下角位置的元素。
访问完6，接下来该怎么办？没错因为6的左子树一定为空，否则它就不可能是第一个被访问的，这时候我们应该判断一下6的右子树是不是为空，如果右子树不为空的话，我们要对它的右子树重复刚才的过程。
对于上面那棵树，它的右子树是空的，于是相当于以6为根结点的子树都已经访问完了，这个时候我们应该回到6的父亲结点，并且访问其父亲结点。
然后重复刚才的过程。
整个过程代码如下：
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root, * pre = p;
if (p) s.push(p);
while (!s.empty()) {
p = s.top();
while (p->left && p->left != pre && p->right != pre) {//没有从左边返回，也没有从右边返回
s.push(p->left);
pre = p;
p = p->left;
}
if (p->right != pre) res.push_back(p->val);
if (p->right && p->right != pre) {
s.push(p->right);
pre = p;
p = p->right;
}
else {
pre = s.top();
s.pop();
}
}
return res;
}
可以和前面的前序遍历做个对比，我们发现，有以下几个区别：
- 对于下面这个循环，也就是在我们往左下角方向走的时候，我们并没有访问中途的结点
//中序
while (p->left && p->left != pre && p->right != pre) {//没有从左边返回，也没有从右边返回
s.push(p->left);
pre = p;
p = p->left;
}
前序遍历过程我们是走一步，就访问一个(访问的过程就是把该结点的值添加到res数组中去)
//前序
while (p->left && p->left != pre && p->right != pre) {//没有从左边返回，也没有从右边返回
res.push_back(p->left->val);
s.push(p->left);
pre = p;
p = p->left;
}
- 对于下面的代码，对应的是我们往右子树方向走之前，如果我们是不是从右孩子返回的（避免从右孩子返回后重复访问当前结点），我们应该先访问当前结点，再往它的右子树方向走。
if (p->right == pre) res.push_back(p->val);
if (p->right && p->right != pre) {
s.push(p->right);
pre = p;
p = p->right;
}
-对于下面的代码，对应的是我们走到了最左下角位置的时候，我们需要确认到达这个位置时，上一个访问过的结点不是右子树，因为从右子树返回的时候，我们当前结点是早就访问过的，中序遍历根结点访问顺序是优先于右子树。
else {
p = s.top(); s.pop();
if (p->right != pre) res.push_back(p->val);
pre = p;
}
整体来看，我们相比前序遍历只是在结点访问顺序上做了一些修改，整体代码逻辑是基本一样的。
后序非递归
后序遍历，是先访问左子树，再访问右子树，最后访问根结点，整体逻辑和上面前序以及中序都是一样的，我就直接解释一下后续非递归的代码了
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root, * pre = p;
if (p) s.push(p);
while (!s.empty()) {
p = s.top();
while (p->left && p->left != pre && p->right != pre) {//没有从左边返回，也没有从右边返回
s.push(p->left);
pre = p;
p = p->left;
}
if (p->right && p->right != pre) {
s.push(p->right);
pre = p;
p = p->right;
}
else {
p = s.top(); s.pop();
pre = p;
res.push_back(p->val);
}
}
return res;
}
由于是最后访问根结点，所以后序遍历的代码在形式上会更加简单。
我们想一想，在后序遍历过程中，什么时候才会输出一个结点，那么必然是访问完一个结点的左子树和右子树之后才会访问该结点。那么当访问完一个结点的左右子树，我们上面的代码其实就是进入到了那个
else {
p = s.top(); s.pop();
pre = p;
res.push_back(p->val);
}
这个我就不多解释了，搞不清楚的可以去自己调试一下。
对于我们上面那棵树，我们的三种遍历序列依次为：
