树的遍历模板

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 前序：根-左-右
void preorder(Node *root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序：左-根-右
void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序：左-右-根
void postorder(Node *root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// 层序遍历（BFS）
void levelOrder(Node *root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *cur = q.front(); q.pop();
        cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

int main() {
    //    1
    //   / \
    //  2   3
    // / \
    //4   5
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    preorder(root);  cout << endl;  // 1 2 4 5 3
    inorder(root);   cout << endl;  // 4 2 5 1 3
    postorder(root); cout << endl;  // 4 5 2 3 1
    levelOrder(root);cout << endl;  // 1 2 3 4 5
    return 0;
}

📖 要点说明

• 前序+中序 或 后序+中序 可唯一确定一棵二叉树
• 层序遍历用队列 BFS 实现
• 记住口诀：前=根在最前，中=根在中间，后=根在最后

⚠️ 常见错误

• 只知道前序+后序不能唯一确定二叉树
• 递归遍历忘写终止条件 if (!root)
• 层序遍历忘处理空树