非递归写法：
对一个节点来说，当遍历它时，要求它的右子树已经遍历完。
因此，为了判断当前节点到底需不需要遍历，引入pLast为上一次遍历的节点。
当pCur->right==pLast||pCur==NULL时，说明右子树已经遍历完了，应该遍历该节点了。
否则，说明该节点右子树尚未遍历，将右子树的根入栈，然后沿着左一直走到头（因为左永远是第一个遍历的）。
class Solution
{
public:
void PostOrderTraver(TreeNode* root)
{
if(!root)
return;
stack<TreeNode*> aux;
TreeNode* pLast=NULL;
TreeNode* pCur=root;
while(pCur)
{
aux.push(pCur);
pCur=pCur->left;
}
while(!aux.empty())
{
pCur=aux.top();
aux.pop();
if(pCur->right==NULL||pCur->right==pLast)
{
cout<<pCur->val<<endl;
pLast=pCur;
}
else
{
aux.push(pCur);
pCur=pCur->right;
while(pCur)
{
aux.push(pCur);
pCur=pCur->left;
}
}
}
return;
}
};
中序遍历：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root)
return vector<int>();
vector<int> ans;
stack<TreeNode*> aux;
aux.push(root);
while(!aux.empty())
{
while(aux.top())
aux.push(aux.top()->left);
aux.pop();
if(!aux.empty())
{
ans.push_back(aux.top()->val);
auto tmp=aux.top()->right;
aux.pop();
aux.push(tmp);
}
}
return ans;
}
};
前序遍历：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root)
return ans;
stack<TreeNode*> aux;
aux.push(root);
while(!aux.empty())
{
while(aux.top())
{
ans.push_back(aux.top()->val);
aux.push(aux.top()->left);
}
aux.pop();
if(!aux.empty())
{
auto it=aux.top()->right;
aux.pop();
aux.push(it);
}
}
return ans;
}
};