对于二叉树的前序遍历，中序遍历以及后序遍历的非递归解法，通常会引入一个栈用来存储二叉树中的节点。?
前序遍历的非递归解法
1.存储根节点的值
2.遍历左子树
3.遍历右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
stack<TreeNode*> q;
//将头节点入栈
q.push(root);
while (!q.empty()) {
//从栈中取出头节点
TreeNode* tmp = q.top();
//将头节点的值置入ret中
ret.push_back(tmp->val);
//由于头节点的值已经取过，将其从栈中删除
q.pop();
//如果左右结点不为空，分别入栈。
//需要注意的是，因为前序遍历的顺序是————根左右
//我们后续需要先对左节点进行操作，而栈是后进先出的
//所以我们应该先入栈右节点，再入栈左节点。
if (tmp->right)
q.push(tmp->right);
if (tmp->left)
q.push(tmp->left);
}
return ret;
}
};使用循环完成前序遍历并不是什么难事，我们并不需要对栈进行什么复杂的操作——从栈中取出一个结点，保存它的值，并将其左右孩子(不为空)入栈，知道栈空。
中序遍历的非递归解法
1.遍历左子树
2.存储根节点的值
3.遍历右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (nullptr == root) {
return ret;
}
stack<TreeNode*> s;
//为了保证树的结构不被破坏，引入另一个变量。
TreeNode* tmp = root;
//由于开始时没有将根节点入栈，所以单独的判空无法进入循环
while (tmp || !s.empty()) {
//如果tmp不为空，将tmp入栈，对齐左孩子重复进行如此操作。
while (tmp) {
s.push(tmp);
tmp = tmp->left;
}
//取出栈首元素，并将其从栈中移除
tmp = s.top();
s.pop();
//存储tmp目前所指的元素的值
ret.push_back(tmp->val);
//令tmp等于其右孩子，如果其右孩子不为空，正好在循环体头部入栈
//反之，跳过了循环直接从栈中取一个元素进行操作
tmp = tmp->right;
}
return ret;
}
};进一步分析：
? ? ? ? 对于有左孩子的节点，我们通过了????????????while (tmp) {
? ? ? ? ? ? ? ? s.push(tmp);
? ? ? ? ? ? ? ? tmp = tmp->left;
? ? ? ? ? ? }将它们进行了统一的入栈，在循环的过程中，除了循环体中入栈的部分，再没有其它操作对任意一个节点进行左孩子的相关操作。并且，出于对右孩子的遍历需要，循环体最后令：
? ? ? ? tmp = tmp->right;
从而规避了某些特殊情况下对左孩子的重复操作。
? ? ? ? 对于有右孩子的节点，我们只在将某个节点的值存储，并将其从栈中删除后，才会进入该节点的右孩子。
若该右孩子没有左孩子，则该节点在入栈后随即便会被取出操作。并且，由于其父节点已经从栈中删除，所以我们并不会再次进入该节点。
若该右孩子有左孩子，则会正常进入循环体将其本身以及左孩子等入栈。
中序遍历的非递归代码中，不需要担心会重复访问某些节点的右孩子。每一个节点被取值后都已经从栈中删除了，这意味着在下一次的循环中我们已经失去了再次进入这个右节点的路标。?
后序遍历的非递归解法
1.遍历左子树
2.遍历右子树
3.存储根节点的值
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
stack<TreeNode*> s;
TreeNode* pre = nullptr;
TreeNode* tmp = root;
while (tmp || !s.empty()) {
while (tmp) {
s.push(tmp);
tmp = tmp->left;
}
tmp = s.top();
//判断右子树是否为空，如是，则代表我们可以直接存储这个节点的值
//如果不为空，我们需要确定一下这个右子树我们是否已经操作过了
if (!tmp->right || tmp->right == pre) {
s.pop();
ret.push_back(tmp->val);
//标记一下该右子树我们已经操作过了
pre = tmp;
//进入到这里表明该节点必定不为空
//如果不将tmp置空后续将会在该节点无限循环下去
tmp = nullptr;
} else {
tmp = tmp->right;
}
}
return ret;
}
};与中序遍历不同，中序遍历中，我们在对根节点进行操作后随即便可以将其从栈中移除，由此避免了重复进入某些节点的问题。
后序遍历中却不可以，我们在取到当前节点之后尚且不能去取它的值，因为后序遍历的顺序是——遍历左子树——遍历右子树——保存根节点的值。
所以我们需要去确认这个节点是否有右孩子，如果有，我们尚需要去遍历其右子树，而后才可以存储当前节点的值。但这随之而来的却还有一个问题——我们该如何确保不会重复进入某个右子树？
一开始是考虑过继续维护一个栈用来存储我们已经进入的右节点，但那样的话实在麻烦。
实际上我们只需要一个空间的指针变量，来记录我们上一个处理完成的右子树即可。
在进行是否存储值得判断时，我们只需要确定这个右子树是否为空，或者这个右子树与我上一次处理的是否是同一个。如果为空，自不必多说。如果与我们上一次处理的是同一个，那么代表当前节点的左右子树都已经完成了遍历，所以直接存储当前节点的值就是了。同时，我们要标记以当前节点为根的子树已经处理完成......
