tree traversal

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
//vector<int> post, in;
vector<node> ans;

int post[] = { 3, 4, 2, 6, 5, 1 };
int in[] = { 3, 2, 4, 1, 6, 5 };


 void pre(int root, int start, int end, int index) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    node temp;
    temp.index = index, temp.value = post[root];
    ans.push_back(temp);
    pre(root  - (end-i+1), start, i - 1, 2 * index + 1);//(root  - (end-i+1)=(root-(end-dividepoint+1))=lefttreeroot
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n = 6;
    /*scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);*/
    pre(n - 1, 0, n - 1, 0);//can use any positive number for index
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i].value;
    }
    return 0;
}

/*
//inOrder+postOrder print preOrder
int post[] = { 3, 4, 2, 6, 5, 1 };
int in[] = { 3, 2, 4, 1, 6, 5 };
//the main point is we can divide the tree to two part with i,left is lefttree,right is righttree.
//useing i in inorder to divide,useing postorder to locate root
void pre(int root, int start, int end) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1); //root - 1 - end + i is the left tree  3    2    4    [1    6    5].for the one loop,the left treerootIndex=allnode-(rightNode+1).currentNode=1

    pre(root - 1, i + 1, end);
}

int main() {
    pre(5, 0, 5);//pre(number of node-1,start,number of node-1)
    return 0;
}*/