c++二叉树怎么建立与遍历

建立二叉树： 可以使用递归或者迭代的方式来建立二叉树。

递归方式建立二叉树：

1. 创建一个二叉树节点结构，包含一个值和指向左右子节点的指针。
2. 使用递归的方式，先建立左子树，再建立右子树。
3. 根据具体需求，确定递归的终止条件。

示例代码如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& nums, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    
    int mid = start + (end - start) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildTree(nums, start, mid - 1);
    root->right = buildTree(nums, mid + 1, end);
    
    return root;
}

TreeNode* buildBinaryTree(vector<int>& nums) {
    return buildTree(nums, 0, nums.size() - 1);
}

迭代方式建立二叉树：

1. 创建一个二叉树节点结构，包含一个值和指向左右子节点的指针。
2. 使用一个队列来辅助建立二叉树。从根节点开始，依次将左右子节点入队列。
3. 根据具体需求，确定迭代的终止条件。

示例代码如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildBinaryTree(vector<int>& nums) {
    if (nums.empty()) {
        return nullptr;
    }
    
    TreeNode* root = new TreeNode(nums[0]);
    queue q;
    q.push(root);
    
    int i = 1;
    while (i < nums.size()) {
        TreeNode* node = q.front();
        q.pop();
        
        if (i < nums.size() && nums[i] != -1) {
            node->left = new TreeNode(nums[i]);
            q.push(node->left);
        }
        
        i++;
        
        if (i < nums.size() && nums[i] != -1) {
            node->right = new TreeNode(nums[i]);
            q.push(node->right);
        }
        
        i++;
    }
    
    return root;
}

遍历二叉树： 常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历（根左右）：

1. 访问根节点。
2. 递归地前序遍历左子树。
3. 递归地前序遍历右子树。

示例代码如下：

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    // 访问根节点
    cout << root->val << " ";
    
    // 前序遍历左子树
    preorderTraversal(root->left);
    
    // 前序遍历右子树
    preorderTraversal(root->right);
}

中序遍历（左根右）：

1. 递归地中序遍历左子树。
2. 访问根节点。
3. 递归地中序遍历右子树。

示例代码如下：

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    // 中序遍历左子树
    inorderTraversal(root->left);
    
    // 访问根节点
    cout << root->val << " ";
    
    // 中序遍历右子树
    inorderTraversal(root->right);
}

后序遍历（左右根）：

1. 递归地后序遍历左子树。
2. 递归地后序遍历右子树。
3. 访问根节点。

示例代码如下：

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;