【C++】非递归实现二叉树的前中后序遍历

简介: 【C++】非递归实现二叉树的前中后序遍历

👉二叉树的前序遍历👈


前序遍历的顺序是根、左子树、右子树。那么首先访问的一定是左路节点,再来访问左路节点的右子树。而访问左路节点的右子树又可以看成一个子问题,那么就能像递归访问整棵树了。


思路:

想定义一个栈st、一个vector v和一个TreeNode* cur,cur初始化为root。

当cur不为空或者st不为空时,while继续。while循环里做一下操作:左路节点入栈的同时尾插到v中,那么左路节点就访问完了。然后取出栈顶节点top,将cur置为top->right,这样就可以转化成子问题去访问左路节点的右子树了。

cur不为空表示要访问一棵树,st不为空表示还有左路节点的右子树没有访问。两个同时为空时,while循环结束,得到正确的前序遍历。

注:一个节点出栈意味着这个节点及其左子树已经访问完了,还剩右子树没有访问。


8448a4c704784db0a9ba8a932d3af556.png

class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        // cur 不为空表示要访问一棵树
        // st 不为空表示还有右子树没有访问
        while(cur || !st.empty())
        {
            // 开始访问整棵树
            // 1.访问左路节点
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            // 转化成子问题:访问左路节点的右子树
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;   // 子问题访问右子树
        }
        return v;
    }
};


f8f3cb8fef7846fe99cefc2a56eec70d.png


👉二叉树的中序遍历👈


中序遍历的顺序是左子树、根、右子树。首先,和中序遍历一样的是左路节点入栈,入栈的同时不能访问该节点,即不能将节点的值尾插到vector中。当左路节点出栈时,表示当前节点的左子树已经访问完了,开始访问当前节点及其右子树。


class Solution 
{
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            // 1.左路节点入栈
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            // 2.当左路节点出栈时,表示左子树已经访问过了,应该
            // 访问这个节点和它的右子树
            TreeNode* top = st.top();
            st.pop();
            v.push_back(top->val);  // 访问这个节点
            cur = top->right;   // 转化成子问题访问右子树
        }
        return v;
    }
};

b6207e09aa4b420e9678182573f604d3.png


👉二叉树的后序遍历👈


后序遍历的顺序是左子树、右子树、根,需要将左子树和右子树访问完了,才能访问根。如果栈顶节点为空或者栈顶节点的右子树已经访问过了,就可以访问栈顶节点了。为了知道是否已经访问过栈顶节点的右子树,我们可以通过prev来记录上一次访问的节点。当prev等于top->right时,表示栈顶节点的右子树已经访问过了,可以弹出栈顶节点并访问它。


4849d797230e42df9909c7cd33f69ffe.png

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();   // 取栈顶节点但不pop
            // 栈顶节点右子树为空或者上一次访问的节点是top右子树的根,说明右子树已经访问过了
            // 可以访问栈顶节点,否则转换成子问题访问top的右子树
            if(top->right == nullptr || top->right == prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
                cur = nullptr;  // cur为空表示弹出的栈顶节点没有右子树或者右子树已经访问过了
            }
            else
                cur = top->right;
        }
        return v;
    }
};


a5bac6be2fb447c0b2c38ff018de6c73.png


👉总结👈


本篇的非递归实现二叉树的前中后序遍历都差不多是一个思路,左路节点先入栈。最大的区别就是栈顶节点的访问时机不同。那么以上就是本篇博客的全部内容了,如果大家觉得有收获的话,可以点个三连支持一下!谢谢大家!💖💝❣️










相关文章
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
4月前
|
存储 C++
【C++】二叉树进阶之二叉搜索树(下)
【C++】二叉树进阶之二叉搜索树(下)
32 4
|
4月前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树(上)
【C++】二叉树进阶之二叉搜索树(上)
36 3
|
4月前
|
算法 C++
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
42 2
|
4月前
|
存储 算法 搜索推荐
|
5月前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
|
5月前
|
算法 C++ 容器
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
239 0
|
5月前
|
C++
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
|
5月前
|
计算机视觉 C++
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
50 0
|
5月前
|
C++ 安全
高效遍历:C++中分隔字符串单词的3种方法详解与实例
拷贝并交换(Copy-and-Swap)是C++中实现赋值操作符和异常安全拷贝构造函数的技巧。它涉及创建临时对象,使用拷贝构造函数,然后交换数据以确保安全。C++11之前的策略在此后及C++11引入的移动语义和右值引用下仍有效,但后者提供了更高效的实现方式。