• 前序遍历：先访问根节点，再遍历左子树，最后右子树（根→左→右）
• 中序遍历：先遍历左子树，再访问根节点，最后右子树（左→根→右）
• 后序遍历：先遍历左子树，再右子树，最后访问根节点（左→右→根）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
<p>// 前序遍历
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}</p><p>// 中序遍历
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}</p><p>// 后序遍历
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}</p>

void preorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
}

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top(); stk.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

void postorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    TreeNode* lastVisited = nullptr;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        if (curr) {
            stk.push(curr);
            curr = curr->left;
        } else {
            TreeNode* peekNode = stk.top();
            if (peekNode->right && lastVisited != peekNode->right) {
                curr = peekNode->right;
            } else {
                cout << peekNode->val << " ";
                lastVisited = stk.top(); stk.pop();
            }
        }
    }
}

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

void levelOrderPerLevel(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl; // 每层换行
    }
}