«

C++二叉树的前序中序后序非递归怎么实现

时间:2024-8-3 07:37     作者:韩俊     分类: Java


这篇“C++二叉树的前序中序后序非递归怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++二叉树的前序中序后序非递归怎么实现”文章吧。

二叉树的前序遍历

前序遍历的顺序是根、左、右。任何一颗树都可以认为分为左路节点,左路节点的右子树。先访问左路节点,再来访问左路节点的右子树。把访问左路节点的右子树看成一个子问题,就可以完整递归访问了。

先定义栈st存放节点、

v
存放值,
TreeNode* cur
,cur初始化为root。

当cur不为空或者栈不为空的时候(一开始栈是空的,cur不为空),循环继续:先把左路节点存放进栈中,同时把值存入v中,一直循环,直到此时的左路节点为空,访问结束。在弹出栈顶元素top,把top->right赋值给我们的cur,就可以转化成子问题去访问左路节点的右子树了。

    栈st不为空说明此时还有左路节点的右子树还没访问,

    cur
    不为空说明此时还有树要去访问。当两个同时为空时,循环结束,最终得到前序遍历。

    一个节点出栈说明这个节点及其左子树已经访问完了,因为我们是先把左路节点存入栈中,此时还剩右子树没有访问。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(!st.empty()||cur)
        {
            //左路节点
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            //左路节点右子树
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;//转化成子问题访问右子树
        }
        return v;
    }
};

二叉树的中序遍历

中序遍历是左、根、右。左子树访问完之后才能去访问根。左路节点一直走直到左子树访问完,入栈的过程中不去进行访问(存放数值到v中),当左路节点出栈之后,也就是从栈中弹出进行访问。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                //不访问
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //进行访问
            v.push_back(top->val);
            st.pop();
            cur = top->right;
        }
        return v;
    }
};

二叉树的后序遍历

后序的遍历顺序是左、右、根。与前面的相比,比较麻烦,我们需要把左子树和右子树访问完再去访问根。我们定义一个栈,在栈里面取到一个节点时:右子树是否访问过,如果没有访问,迭代子问题访问,如果访问过了,则访问这个根节点,pop出栈

如果top的右子树为空或者右子树已经访问过了(上一个访问节点是右子树的根),那么说明右子树不用访问或者访问过了,可以访问根top;当右子树不为空,且没有访问过,则迭代子问题访问。

通过

prev
来判断上一次访问的节点:如果
prev
等于
top->right
时,表示栈顶节点的右子树已经访问过了,可以弹出栈顶节点并访问它。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        TreeNode*prev = nullptr;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //top的右子树为空,或者右子树已经访问过了(上一个访问节点时右子树的根)那么说明右子树不用访问或者访问过了,可以访问根top
            //右子树不为空,且没有访问, 则迭代子问题访问
            if(top->right==nullptr||top->right==prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};

标签: java

热门推荐