二叉树先序遍历

Paste_Image.png

Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:（输出为后序遍历）
3 4 2 6 5 1

这个问题中，push的顺序实际上就是先序遍历的顺序——对于非递归先序遍历，算法流程为从根节点出发，一边沿左孩子访问访问一边将右孩子节点收入到栈中，当左孩子访问到末尾，即left=NULL时，从栈中弹出一个元素继续执行，直至栈空

对于这个问题，可以看出对于沿左路一路push的操作，实际上就是先序遍历操作——首先从根节点开始按照VLR的顺序进行访问，如果检测到push操作就将当前节点初始化，然后设置为输入的数字，如果为pop就设置为NULL，递归调用左右孩子节点即可。

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int N;
class Node {
public:
    int num;
    Node* left;
    Node* right;
    Node() {
        left = NULL;
        right = NULL;
    }
};
int counter = 0;
string op;
int num;
Node* preOrder() {
    Node* root = NULL;
    if (counter < 2 * N) {
        cin >> op;
        if (op.length() == 4)
        {
            cin >> num;
            root = new Node();
            root->num = num;
            counter++;
        }
        if (op.length() == 3)
        {
            counter++;
            return NULL;
        }
        root->left = preOrder();
        root->right = preOrder();
    }
    return root;
        
}
vector<int>post;
void postOrder(Node* root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        post.push_back(root->num);
    }
}
int main()
{

    cin >> N;
    Node* root = preOrder();
    postOrder(root);
    cout << post[0] ;
    for (int i = 1; i < N; i++)
    {
        cout << ” ” << post[i] ;
    }
    cout << endl;
    return 0;
}