C++二叉树的 前中后序遍历（学C++必看必会）深度优先遍历详解

C++二叉树的 前中后序遍历（学C++必看必会）深度优先遍历详解 二叉树的递归遍历

代码随想客

前序遍历

class Solution {
public:
    //定义一个遍历函数
    void travel(TreeNode* cur,vector& res)
    {
        if(cur==nullptr)
        {
            return ;
        }
        //前序就是中左右
        res.push_back(cur->val);
        travel(cur->left,res);
        travel(cur->right,res);
    }

    vector preorderTraversal(TreeNode* root) 
    {
        vector res;
        travel(root,res);
        return res;    
    }
};

中序遍历

class Solution {
public:
    //定义一个遍历函数
    void travel(TreeNode* cur,vector& res)
    {
        if(cur==nullptr)
        {
            return ;
        }
        //中序就是左中右
        travel(cur->left,res);
        res.push_back(cur->val);
        travel(cur->right,res);
    }

    vector preorderTraversal(TreeNode* root) 
    {
        vector res;
        travel(root,res);
        return res;    
    }
};

后序遍历

class Solution {
public:
    //定义一个遍历函数
    void travel(TreeNode* cur,vector& res)
    {
        if(cur==nullptr)
        {
            return ;
        }
        //后序就是左右中
        travel(cur->left,res);
        travel(cur->right,res);
        res.push_back(cur->val);
    }

    vector preorderTraversal(TreeNode* root) 
    {
        vector res;
        travel(root,res);
        return res;    
    }
};

二叉树的迭代遍历

代码随想客

前序遍历（迭代法）

class Solution {
public:
    vector preorderTraversal(TreeNode* root) 
    {
        stack st;
        vector res;
        if(root==nullptr)
        {
            return res;
        }
        st.push(root);
        while(!st.empty())
        {
            TreeNode* node=st.top();
            st.pop();
            res.push_back(node->val);
            if(node->right)
            {
                st.push(node->right);
            }
            if(node->left)
            {
                st.push(node->left);
            }
        }
        return res;
    }
};

中序遍历（迭代法）

class Solution {
public:
    vector inorderTraversal(TreeNode* root) 
    {
        vector res;
        stack st;
        if(root==nullptr)
        {
            return res;
        }
        TreeNode* cur=root;
        while(cur!=nullptr||!st.empty())
        {
            if(cur!=nullptr)
            {
                st.push(cur);
                cur=cur->left;
            }
            else
            {
                cur=st.top();
                res.push_back(st.top()->val);
                st.pop();
                cur=cur->right;
            }
        }
        return res;

    }
};

后序遍历（迭代法）

class Solution {
public:
    vector postorderTraversal(TreeNode* root) 
    {
        vector res;
        stack st;
        TreeNode* node;
        if(root==nullptr)
        {
            return res;
        }
        st.push(root);
        while(!st.empty())
        {
            node=st.top();
            st.pop();
            res.push_back(node->val);
            if(node->left)
            {
                st.push(node->left);
            }
            if(node->right)
            {
                st.push(node->right);
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

二叉树的统一迭代遍历（看不懂也要背下来）

代码随想客

统一迭代遍历基本结构如下

vector res;
stack st;
//首先判断根节点是否为空，非空则压入st
if(root!=nullptr)
{
	st.push(root);
}
//然后就是主结构
while(!st.empty())
{
	TreeNode* node=root;
	if(node!=nullptr)
	{
		st.pop();  //首先先d出，避免重复 *** 作
		//前序就是反过来：右左中，且每次到中就加一个nullptr
		//中序就是反过来：右中左，且每次到中就加一个nullptr
		//后序就是反过来：中右左，且每次到中就加一个nullptr	
	}
	else
	{
		//这里上来就是一个pop(),d掉空指针
		st.pop();
		//然后把top的指针指向的值push_back进res
		res.push_back(st.top->val);
		//然后再是一个pop()
		st.pop();
	}
}
//最后一个非常简单的return
return res;

前序遍历（统一迭代）

class Solution {
public:
    vector inorderTraversal(TreeNode* root) 
    {
        vector res;
        stack st;
        if(root!=nullptr)
        {
            st.push(root);
        }
        while(!st.empty())
        {
            TreeNode* node=st.top();
            if(node!=nullptr)
            {
                st.pop();
                if(node->right)
                {
                    st.push(node->right);
                }
                st.push(node);
                st.push(nullptr);  //中节点被访问过，但是还没有处理，加入空节点作为标记
                if(node->left)
                {
                    st.push(node->left);
                }
            }
            else//只有当遇到空节点是，才将下一节点放进res
            {
                st.pop();//d掉空节点
                res.push_back(st.top()->val);
                st.pop();//用过后把它d掉
            }
        }
        return res;
    }
};

中序遍历（统一迭代）

class Solution {
public:
    vector preorderTraversal(TreeNode* root) 
    {
        vector res;
        stack st;
        if(root!=nullptr)
        {
            st.push(root);
        }
        while(!st.empty())
        {
            TreeNode* node=st.top();
            if(node!=nullptr)
            {
                st.pop();
                if(node->right)
                {
                    st.push(node->right);// 右
                }
                if(node->left)
                {
                    st.push(node->left);//  左
                }
                st.push(node);          //  中
                st.push(nullptr);

            }
            else
            {
                st.pop();
                res.push_back(st.top()->val);
                st.pop();
            }
        }
        return res;
    }
};

后序遍历（统一迭代）

class Solution {
public:
    vector postorderTraversal(TreeNode* root) 
    {
        vector res;
        stack st;
        if(root!=nullptr)
        {
            st.push(root);
        }
        while(!st.empty())
        {
            TreeNode* node=st.top();
            if(node!=nullptr)
            {
                st.pop();
                st.push(node);//    中
                st.push(nullptr);

                if(node->right)
                {
                    st.push(node->right);// 右
                }
                if(node->left)
                {
                    st.push(node->left);//  左
                }
            }
            else
            {
                st.pop();
                res.push_back(st.top()->val);
                st.pop();

            }
        }
        return res;
    }
};