提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

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

二叉树遍历递归 实现 中序 后序 前序
2023-06-13 09:16:13 时间

阿里二面的算法题

非递归写法

前序遍历

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;
    }
}

中序遍历

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;
    }
}

后序遍历

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;
        }
    }
}

相关文章