后序遍历非递归法
后续遍历，非递归法相对于前中序稍微复杂一点，因为它需要记录当前节点是否已经遍历过了。
三种方法：1）使用prev，记录输出的前一个节点 2）使用visible方法【直接记录当前节点是否访问过】。
3）对于这些非递归法，都可以使用颜色法【准备第二个栈，表示当前节点是否访问过，若访问过，直接输出】。
1.常规方法
左中右、左中右、左右中。
都是先对左节点做处理，因此可以先把左节点放到栈里。
然后取出一个节点，考虑处理右节点。【比较难理解】
需要注意
主要元素：栈、root
root 当前待遍历节点。 栈：取出下一个节点
如果右节点没有的话，或者无需向右遍历，那就把root置为空指针
/**
* 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) {
//左右中
stack<TreeNode* > mem;
vector<int>res;
if(!root)
return res;
TreeNode* pre=nullptr;
while(root||!mem.empty()){
while(root){//先把root左节点加入
mem.push(root);
root=root->left;
}
root=mem.top();
mem.pop();
//加右节点，前提
if(root->right==pre||root->right==nullptr){//右节点已经遍历
res.push_back(root->val);
pre=root;
root=nullptr;
}else{//右节点先处理
mem.push(root);
root=root->right;
}
//可以用visible来表示，不用visible就得用pre指针
}
return res;
}
};
2.使用visible思路，而非prev指针。
总之先遍历每一个节点的左树。然后对当前情况分组处理。1.是当前节点已被访问过。直接输出。否则，先看当前节点和它的右节点。
/**
* 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) {
//左右中
stack<TreeNode* > mem;
map<TreeNode* ,int> a;
vector<int>res;
if(!root)
return res;
TreeNode* pre=nullptr;
while(root||!mem.empty()){
while(root){//先把root左节点加入
mem.push(root);
a[root]=1;
root=root->left;
}
root=mem.top();
mem.pop();
if(a[root]>1||!root->right){
res.push_back(root->val);
root=nullptr;
}else{
mem.push(root);
a[root]=2;
root=root->right;
}
}
return res;
}
};
3.颜色标记法。【实际上是中右左换成左右中】
可以使用两个栈，或者使用pair对。
左右中——》重新push时是 中左右，入栈。
开始先把节点push到栈中（但是只是辅助遍历，并不输出）
然后从栈中取出节点，按照中 左 右的顺序重新push（中节点，因为取出过一次，认为已经处理过，就标记处理过，再取出时直接输出就可）,没有处理过的，继续按照中左右顺序遍历。
【这里新加一个栈，存标记，也可以用pair对】
/**
* 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) {
//左右中
stack<TreeNode*> res;
stack<int> biaoji;
vector<int> rr;
if(!root)
return rr;
res.push(root);
biaoji.push(1);
TreeNode* tmp;
int tmpb;
while(!res.empty()){
tmp=res.top();
tmpb=biaoji.top();
res.pop();
biaoji.pop();
//cout<<tmp->val<<"\t"<<tmpb<<endl;
if(tmpb==1){
res.push(tmp);
biaoji.push(2);
if(tmp->right){
res.push(tmp->right);
biaoji.push(1);
}
if(tmp->left){
res.push(tmp->left);
biaoji.push(1);
}
}else{
rr.push_back(tmp->val);
}
}
return rr;
}
};
前序遍历【中左右】
/**
* 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> res;
if(!root){
return res;
}//中左右
stack<TreeNode*> tmp;
while(root||!tmp.empty()){
while(root){
tmp.push(root);
res.push_back(root->val);
root=root->left;
}
root = tmp.top();
tmp.pop();
//看右
if(root->right){
root=root->right;
}else{
root=nullptr;
}
}
return res;
}
};
中序遍历【左中右】
/**
* 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> res;
if(!root){
return res;
}//左中右
stack<TreeNode*> tmp;
while(root||!tmp.empty()){
while(root){
tmp.push(root);
root=root->left;
}
root = tmp.top();
tmp.pop();
res.push_back(root->val);
//看右
if(root->right){
root=root->right;
}else{
root=nullptr;
}
}
return res;
}
};
网友评论