二叉树的遍历（前序 / 中序 / 后序）
从'按什么顺序访问每个结点'出发，彻底搞懂先序、中序、后序和层序

#include <iostream>
#include <string>
using namespace std;
struct TreeNode { int val; TreeNode *l,*r; TreeNode(int v):val(v),l(nullptr),r(nullptr){} };
int pos = 0;
TreeNode* build(const string a[], int n) {
    if (pos >= n) return nullptr;
    string s = a[pos++];
    if (s == "#") return nullptr;
    TreeNode* t = new TreeNode(stoi(s));
    t->l = build(a, n); t->r = build(a, n);
    return t;
}
void pre(TreeNode* r)  { if (!r) return; cout << r->val << " "; pre(r->l);  pre(r->r);  }
void in(TreeNode* r)   { if (!r) return; in(r->l);  cout << r->val << " "; in(r->r);   }
void post(TreeNode* r) { if (!r) return; post(r->l); post(r->r); cout << r->val << " "; }
int main() {
    string a[] = {"1","2","4","#","#","5","#","#","3","#","6","#","#"};
    int n = sizeof(a) / sizeof(a[0]);
    TreeNode* root = build(a, n);
    cout << "先序："; pre(root);  cout << endl;
    cout << "中序："; in(root);   cout << endl;
    cout << "后序："; post(root); cout << endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct TreeNode { int val; TreeNode *l,*r; TreeNode(int v):val(v),l(nullptr),r(nullptr){} };
int pos = 0;
TreeNode* build(const string a[], int n) {
    if (pos >= n) return nullptr;
    string s = a[pos++];
    if (s == "#") return nullptr;
    TreeNode* t = new TreeNode(stoi(s));
    t->l = build(a, n); t->r = build(a, n);
    return t;
}
void level(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        TreeNode* u = q.front(); q.pop();
        cout << u->val << " ";
        if (u->l) q.push(u->l);
        if (u->r) q.push(u->r);
    }
}
int main() {
    string a[] = {"1","2","4","#","#","5","#","#","3","#","6","#","#"};
    int n = sizeof(a) / sizeof(a[0]);
    TreeNode* root = build(a, n);
    cout << "层序："; level(root); cout << endl;
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct TreeNode { int val; TreeNode *l,*r; TreeNode(int v):val(v),l(nullptr),r(nullptr){} };
int pos = 0;
TreeNode* build(const string a[], int n) {
    if (pos >= n) return nullptr;
    string s = a[pos++];
    if (s == "#") return nullptr;
    TreeNode* t = new TreeNode(stoi(s));
    t->l = build(a, n); t->r = build(a, n);
    return t;
}
void pre_nr(TreeNode* root) {       // 非递归先序：用栈模拟递归
    if (!root) return;
    stack<TreeNode*> st; st.push(root);
    while (!st.empty()) {
        TreeNode* u = st.top(); st.pop();
        cout << u->val << " ";
        if (u->r) st.push(u->r);    // 右孩子后访问，先入栈
        if (u->l) st.push(u->l);
    }
}
int main() {
    string a[] = {"1","2","4","#","#","5","#","#","3","#","6","#","#"};
    int n = sizeof(a) / sizeof(a[0]);
    TreeNode* root = build(a, n);
    cout << "非递归先序："; pre_nr(root); cout << endl;
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 由先序 pre 与中序 in 重建二叉树，并输出后序
int pre_i = 0;
void rebuild(const vector<int>& in, int l, int r,
             const vector<int>& pre, string& post) {
    if (l > r) return;
    int root = pre[pre_i++];          // 先序第一个就是根
    int mid = l;
    while (in[mid] != root) mid++;     // 在中序里找到根的位置
    rebuild(in, l, mid - 1, pre, post);   // 递归左子树
    rebuild(in, mid + 1, r, pre, post);   // 递归右子树
    post += to_string(root) + " ";        // 最后访问根 → 后序
}
int main() {
    vector<int> pre = {1, 2, 4, 5, 3, 6};
    vector<int> in  = {4, 2, 5, 1, 3, 6};
    string post = "";
    rebuild(in, 0, (int)in.size() - 1, pre, post);
    cout << "后序：" << post << endl;
    return 0;
}

#include <iostream>
using namespace std;
struct TreeNode {
    char op; int val; bool isNum;
    TreeNode *l, *r;
    TreeNode(char o) : op(o), isNum(false), l(nullptr), r(nullptr) {}
    TreeNode(int v) : val(v), isNum(true), l(nullptr), r(nullptr) {}
};
void pre(TreeNode* r)  { if(!r) return; cout << (r->isNum?to_string(r->val):string(1,r->op)) << " "; pre(r->l);  pre(r->r);  }
void in(TreeNode* r)   { if(!r) return; in(r->l);  cout << (r->isNum?to_string(r->val):string(1,r->op)) << " "; in(r->r);   }
void post(TreeNode* r) { if(!r) return; post(r->l); post(r->r); cout << (r->isNum?to_string(r->val):string(1,r->op)) << " "; }
int main() {
    // 表达式 (1+2)*3 的二叉树
    TreeNode* root = new TreeNode('*');
    root->l = new TreeNode('+'); root->r = new TreeNode(3);
    root->l->l = new TreeNode(1); root->l->r = new TreeNode(2);
    cout << "前缀（先序）："; pre(root);  cout << endl;
    cout << "中缀（中序）："; in(root);   cout << endl;
    cout << "后缀（后序）："; post(root); cout << endl;
    return 0;
}