二叉树遍历操作

// 二叉树常见面试问题汇总
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
class TreeNode
{
public:
    TreeNode(int val): val(val), left(nullptr),right(nullptr){}
    int val;
    TreeNode* left;
    TreeNode* right;
};
//前序遍历非递归
void preOrder1(TreeNode* root, vector<int> &res)
{
    if (root != nullptr)
    {
        res.push_back(root->val);
        preOrder1(root->left, res);
        preOrder1(root->right,res);
    }
    return;
}
/*
    前序遍历非递归
    1、从根节点开始，遍历所有的根节点的左子树的左孩子，将他们都放入到栈中。
    2、出栈。
    3、逐个取出栈中的元素，该元素的左子树肯定已经遍历过了，要检查是不是有右子节点，有的话，将右子节点按照步骤1走一遍（相当于以该右子节点为新的根节点进行了同样的遍历）
*/
void preOrder(TreeNode* root, vector<int> &res)
{
    if (root == nullptr)
    {
        return;
    }
    stack<TreeNode*> s;
    TreeNode * p = root;
    while (p != nullptr || !s.empty())
    {
        //从根节点开始，遍历所有的根节点的左子树的左孩子，将他们都放入到栈中
        while (p != nullptr)
        {
            s.push(p);
            res.push_back(p->val); //先遍历根节点的元素
            p = p->left;
        }
        if (!s.empty())
        {
            p = s.top(); //取出栈顶元素，此时元素的左边应该都已经遍历过了，需要遍历其右边的
            s.pop();
            p = p->right; //下一次循环就会遍历以该节点为根节点的树
        }
    }
    return;
}
//递归中序遍历
void inOrder1(TreeNode* root, vector<int> &res)
{
    if (root != nullptr)
    {
        inOrder1(root->left, res);
        res.push_back(root->val);
        inOrder1(root->right, res);
    }
}
/*
    中序遍历非递归
    1、先将根节点入栈，遍历左子树
    2、第一遍循环遍历完左子树返回后，此时栈顶元素为左子树的最左边的元素，此节点没有左子树，相当于左子树已经遍历完了，此时打印该节点的值
    3、然后以该节点的右子节点作为新的跟节点进行下一轮中序遍历循环
*/
void inOrder(TreeNode* root, vector<int> &res)
{
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != nullptr || !s.empty())
    {
        while (p != nullptr)
        {
            s.push(p);
            p = p->left;
        }
        //取出栈中的元素，查看其右子节点
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            res.push_back(p->val);
            p = p->right;
        }
    }
    return;
}
//后序遍历递归
void postOrder1(TreeNode* root, vector<int>& res)
{
    if (root != nullptr)
    {
        postOrder1(root->left, res);
        postOrder1(root->right, res);
        res.push_back(root->val);
    }
    return;
}
//后序遍历非递归
/*
    后序遍历要求在遍历完左右子树之后再访问根，需要判断根节点的左右子树是否均遍历过。
    采用标记法，节点入栈时，表示第一次入栈，然后遍历左子树，返回后，修改栈顶元素的访问标记为非第一次访问，然后遍历其右边子树，最后访问根节点。
*/
//辅助结构，增加访问次数标记
class Node
{
public:
    TreeNode* btNode;
    bool isFirst;
};
void postOrder(TreeNode* root, vector<int> &res)
{
    stack<Node*> s;
    TreeNode* p = root;
    Node* popNode; //栈顶出栈的元素
    while (p != nullptr || !s.empty())
    {
        //将左子树压栈
        while (p != nullptr)
        {
            Node* curNode = new Node();
            curNode->btNode = p;
            curNode->isFirst = true;
            s.push(curNode);
            p = p->left;
        }
        if (!s.empty())
        {
            popNode = s.top();
            //先查看是否第一次出栈，如果是第一次，还需要将右子节点进行遍历
            if (popNode->isFirst)
            {
                popNode->isFirst = false;
                p = popNode->btNode->right; //将右子节点作为新的根节点，进行下一轮的遍历。
            }
            else //左右子树都已经遍历过了
            {
                s.pop();
                res.push_back(popNode->btNode->val);
                p = nullptr;
            }
        }
    }
}
//二叉树层序遍历
/*
    借助队列：
    假如层序遍历为A、B、C、D、E、F、G
            A
        B       C
      D   E   F    G
    1、A入队
    2、A出队，同时A的子节点B、C入队（此时队列有B、C）
    3、B出队，同时B的子节点D、E入队（此时队列由C、D、E）
    4、C出队，同时C的子节点F、G入队（此时队列有D、E、F、G）
*/
void LevelOrder(TreeNode* root, vector<int> &res)
{
    queue<TreeNode*> q;
    TreeNode* p;
    q.push(root);       //根节点入队
    while (!q.empty())
    {
        p = q.front();
        q.pop();
        res.push_back(p->val);
        if (p->left)            //当前节点有左节点，则左节点入队
        {
            q.push(p->left);
        }
        if (p->right)           //当前节点有右节点，则右节点入队
        {
            q.push(p->right);
        }
    }
    return;
}
int main()
{
    //创建二叉树
    TreeNode* root = new TreeNode(1);
    TreeNode* curNode = root;
    curNode->left = new TreeNode(2);
    curNode->right = new TreeNode(3);
    curNode->left->left = new TreeNode(4);
    curNode->left->right = new TreeNode(5);
    curNode->right->left = new TreeNode(6);
    curNode->right->right = new TreeNode(7);
    vector<int> res;
    postOrder(root, res);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}