题解 | 先序遍历、中序遍历和后序遍历

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<vector<int>> children(n+1);
    vector<int> parent(n+1,0);
    int a,b;
    for (int i=0;i<n-1;i++) { // 注意 while 处理多个 case
        cin>>a>>b;
        children[a].push_back(b);
        parent[b]=a;
    }
    vector<int> leftNode(n+1,0);
    vector<int> rightNode(n+1,0);
    for(int i=1;i<=n;i++){
        int childrenNum = children[i].size();
        if(childrenNum==0)
            continue;
        if(childrenNum==1){
            if(children[i][0]>i)
                leftNode[i]=children[i][0];
            else
                rightNode[i]=children[i][0];
        }
        else{
            sort(children[i].begin(),children[i].end());
            leftNode[i]=children[i][0];
            rightNode[i]=children[i][1];
        }
    }
    int root=0;
    for(int i=1;i<n+1;i++){
        if(parent[i]==0){
            root=i;
            break;
        }  
    }
    // cout<<root<<endl;
    //先序
    vector<int> pre;
    stack<int> st_pre;
    st_pre.push(root);
    while(!st_pre.empty()){
        int curr = st_pre.top();
        st_pre.pop();
        pre.push_back(curr);

        if(rightNode[curr]!=0) st_pre.push(rightNode[curr]);
        if(leftNode[curr]!=0) st_pre.push(leftNode[curr]);
    }
    for(int i=0;i<pre.size();i++){
        cout<<pre[i]<<' ';
    }
    cout<<endl;
    //中序
    vector<int> in;
    stack<int> st_in;
    int curr_in = root;
    while(curr_in!=0||!st_in.empty()){
        //左子树全入栈
        while(curr_in!=0){
            st_in.push(curr_in);
            curr_in = leftNode[curr_in];
        }
        curr_in = st_in.top();
        st_in.pop();
        in.push_back(curr_in);
        curr_in = rightNode[curr_in];
    }
    for(int i=0;i<in.size();i++){
        cout<<in[i]<<' ';
    }
    cout<<endl;
    //后序
    vector<int> post;
    stack<int> st_post;
    int curr_post=root;
    int last=0;
    while(curr_post!=0||!st_post.empty()){
        while(curr_post!=0){
            st_post.push(curr_post);
            curr_post = leftNode[curr_post];
        }
        int top_node = st_post.top();
        if(rightNode[top_node]==0||rightNode[top_node]==last){
            post.push_back(top_node);
            st_post.pop();
            last = top_node;
            curr_post = 0;
        } else{
            curr_post = rightNode[top_node];
        }
    }
    for(int i=0;i<post.size();i++){
        cout<<post[i]<<' ';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")