二叉树前序，中序，后序遍历的非递归实现

阿里二面的算法题

非递归写法

前序遍历

代码语言：javascript复制

void pretOrder(TreeNode *root){
    if(root==nullptr) return root;

    TreeNode *p=root;
    stack<TreeNodr *> st;

    while(p || !st.empty()){
        while(p){
            st.push(p);
            cout<<p->val;
            p=p->left;
        }

        p=st.top();
        st.pop();
        p=p->right;
    }
}

中序遍历

代码语言：javascript复制

void inOrder(TreeNode *root){
    if(root==nullptr) return root;

    TreeNode *p=root;
    stack<TreeNodr *> st;

    while(p || !st.empty()){
        while(p){
            st.push(p);
            p=p->left;
        }

        p=st.top();
        cout<<p->val;
        st.pop();
        p=p->right;
    }
}

后序遍历

代码语言：javascript复制

void postOrder(TreeNode *root){
    if(root==nullptr) return root;

    TreeNode *p=root;
    TreeNode *r=nullptr;  //记录最近访问的节点
    stack<TreeNodr *> st;

    while(p || !st.empty()){
        while(p){
            st.push(p);
            p=p->left;
        }

        p=st.top();
        if(p->right && p->right!=r){
            p=p->right;
        }
        else{
            st.pop();
            cout<<p->val;
            r=p;
            p=nullptr;
        }
    }
}

遍历 递归

0 人点赞