非递归的三种序列遍历

---

1.先序遍历：

//先序遍历
void preorder(Node* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    Node* p = root;
    stack<Node*> s;
    while (!s.empty() || p)
    {
        while(p!=NULL){
            printf("%d",p->num);
            s.push(p);
            p=p->left;
        }
        if(!s.empty()){
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}

2.中序遍历：

如果stack为空且指针为NULL则退出循环。
先访问左指针，非空则无限循环到NULL。
再取栈顶元素（如果非空的话）并printf，然后替换p为p->right

image.png

//中序遍历
void inorder(Node* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    Node* p = root;
    stack<Node*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->left;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            // 抛掉拐点，避免重复left循环，进入右子树
            cout << p->num;
            p = p->right;
        }
    }
}

3. 后序遍历：https://blog.csdn.net/GSCurry/article/details/77993483

pre指向上一次打印的节点，p当沿着左侧向上迭代的时候保持null被封印，直到下一个右分支存在左分支才非空。

peek摘取stack栈顶元素，决定是否往右（如果右侧未被遍历pre!=peek->right），因为往左已经到了尽头。如果往右也是尽头那么打印，pre=peek阻止打印右侧已被打印的元素。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if(root==NULL){
            return res;
        }
        vector<TreeNode*>s;
        TreeNode *p=root;
        TreeNode * pre=NULL;
        while(!s.empty()||p){
            while(p){
                s.push_back(p);
                pre=p;
                p=p->left;
            }
            TreeNode*peek=s.back();
            if(peek->right==NULL||peek->right==pre){
                res.push_back(peek->val);
                pre=peek;
                s.pop_back();
            }
            else{
                p=peek->right;
            }
        }
        return res;
    }
};

不用临时变量peak也行：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root==nullptr){
            return {};
        }
        TreeNode*pre=root;
        TreeNode*now=root;
        vector<int>res;
        vector<TreeNode*>stack;
        stack.push_back(root);
        now=now->left;
        while(!stack.empty()){
            while(now!=nullptr){
                stack.push_back(now);
                pre=now;
                now=now->left;
            }
            now=stack.back();
            if(now->right==nullptr||now->right==pre){
                res.push_back(now->val);
                pre=now;
                stack.pop_back();
                now=nullptr;
            }else{
                pre=now;
                now=now->right;
            }
        }
        return res;
    }
};