二叉树具有前序、中序、后序三种遍历方式。递归的相信大家都会写，但是迭代的该怎么写呢？怎样的迭代写法才能具有统一性便于理解呢？请看下面具体的做法，每种遍历方式各有2种策略，基于栈的和基于游标指针，使用栈来辅助的。
1.前序遍历
不采用游标指针的做法
void preOrder(TreeNode* root,vector<int>& res){
if(root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();st.pop();
res.push_back(cur->val);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
return;
}
采用游标指针的做法
void preOrder(TreeNode* root,vector<int>& res){
if(root == nullptr) return;
stack<TreeNode*> st;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr){
if(cur){
res.push_back(cur->val);
st.push(cur);
cur = cur->left;
}else{
cur = st.top();st.pop();
cur = cur->right;
}
}
return;
}
2.中序遍历
不采用游标指针的做法，这里只能贴个错误的，因为目前看没有这样的解法
void inOrder2(TreeNode* root,vector<int>& res){
if(root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
TreeNode* pre = root;
while (!st.empty()) {
TreeNode* p = st.top();
if(p->left && pre != p->left){//这里很难判断左子树是否被访问过,除非你每个节点搞个变量
st.push(p->left);
}else{
st.pop();
res.push_back(p->val);
pre = p;
if(p->right) {
st.push(p->right);
}
}
}
return ;
}
采用游标指针的做法
void inOrder(TreeNode* root,vector<int>& res){
if(root == nullptr) return;
stack<TreeNode*> st;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr){
if(cur){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();st.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return;
}
3.后序遍历
不采用游标指针的做法
void postOrder(TreeNode* root,vector<int>& res){
if(root == nullptr) return;
stack<TreeNode*> st;
TreeNode* pre = root;//
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
// pre = cur->left说明cur没有右子树 ，也可以处理cur了
if((cur->left == nullptr && cur->right == nullptr)
||pre == cur->left||pre == cur->right){
res.push_back(cur->val);
st.pop();
pre = cur;
}else{
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
}
return;
}
采用游标指针的做法
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(root == nullptr) return res;
TreeNode* cur = root;
TreeNode* pre = root;
stack<TreeNode*> st;
while(st.empty() == false || cur != nullptr){
if(cur != nullptr){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();
if(cur->right == nullptr || cur->right == pre){
res.push_back(cur->val);
st.pop();
pre = cur;
cur = nullptr;
}else{
cur = cur->right;
}
}
}
return res;
}
总结一下这2种策略的差别以及关键——基于栈的策略，就想办法在每一次迭代处理好栈；基于游标指针的策略，就在每一步处理好游标指针，只在需要的时候去处理辅助栈。听起来像是废话，但是带着这2句话反过头来看代码，会有感悟的。
衣带渐宽终不悔，为伊消得人憔悴。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
