第一关 二叉树的创建及遍历输出 二叉树创建，可以通过输入二叉树的先根序序列（完整的），根据先根序序列进行创建，。二叉树的遍历则有先根序、中根序、后根序，按层次等方式。第二关 实现二叉树中树叶结点计数、左右子树互换算法； 二叉树左右子树互换。用c++实现，给出完整代码，能实现输出

在C++中，我们可以首先定义一个简单的二叉树节点结构，然后利用递归的方式创建二叉树。这里是一个基本的二叉树节点类定义以及创建和遍历的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建二叉树函数，给定先根序序列
TreeNode* createTree(vector<int>& preorder) {
    if (preorder.empty()) return nullptr;

    // 找到根节点（通常是序列的第一个元素）
    TreeNode* root = new TreeNode(preorder[0]);

    // 分别处理左子树和右子树
    int i = 1;
    for (; i < preorder.size(); ++i) {
        if (preorder[i] < preorder[0]) {
            root->left = createTree(preorder.begin() + i);
            break;
        }
    }

    // 后面的元素作为右子树
    if (i != preorder.size()) {
        root->right = createTree(preorder.begin() + i);
    }

    return root;
}

// 遍历二叉树
void printTree(TreeNode* root, string traversalType = "Preorder") {
    if (root == nullptr) return;

    switch (traversalType) {
    case "Preorder":
        cout << root->val << " ";
        printTree(root->left);
        printTree(root->right);
        break;
    case "Inorder":
        printTree(root->left);
        cout << root->val << " ";
        printTree(root->right);
        break;
    case "Postorder":
        printTree(root->left);
        printTree(root->right);
        cout << root->val << " ";
        break;
    default:
        cout << "Invalid traversal type" << endl;
    }
}

// 计算叶子节点并交换左右子树
void countLeavesAndSwap(TreeNode*& root) {
    if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {
        // 如果是叶子节点，增加计数
        static int leafCount = 0;
        leafCount++;
        return;
    }

    // 递归计算左子树和右子树的叶子节点
    countLeavesAndSwap(root->left);
    countLeavesAndSwap(root->right);

    // 交换左右子树
    swap(root->left, root->right);
}

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3}; // 示例先根序序列
    TreeNode* root = createTree(preorder);

    cout << "Preorder Traversal: ";
    printTree(root, "Preorder");
    cout << "\nLeaf Count: " << leafCount << endl; // 先计算叶子节点

    // 交换左右子树
    countLeavesAndSwap(root);

    cout << "After swapping:\n";
    cout << "Postorder Traversal: ";
    printTree(root, "Postorder"); // 输出交换后的后根序遍历结果

    return 0;
}

这个程序实现了二叉树的创建、预顺序遍历、计数叶子节点以及交换左右子树的功能。运行`main()`函数可以看到相应的操作效果。