给定⼀个⼆叉树的根节点 root，返回它的 中序 遍历。用C++实现

中序遍历是指，以 root 为根节点，先遍历 root 的左子树，再遍历 root 节点，最后遍历 root 的右子树。用 C 语言实现的话，可以这样： void inOrder(TreeNode *root) {
if (root == NULL)
return;
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}

相关问题

判断完全二叉树 【问题描述】 给定一棵树的前序遍历和中序遍历，判断该树是否为完全二叉树 【输入形式】 一棵树的前序遍历和中序遍历 写出C++代码

判断一棵树是否为完全二叉树，通常需要结合前序遍历和中序遍历的特点。前序遍历（根节点 -> 左子树 -> 右子树）和中序遍历（左子树 -> 根节点 -> 右子树）对于确定二叉树的结构非常有帮助。

这里有一个基本的算法步骤：
1. 对于前序遍历，第一个元素是根节点，这将用于定位在中序遍历中的位置。
2. 中序遍历可以帮助我们找到根节点及其左右子树的范围。
3. 通过比较这两个遍历序列，我们可以确认是否有任何节点未在其父节点的右子树中。

以下是一个简单的C++函数，用于判断是否为完全二叉树：

#include <vector>
using namespace std;

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

bool isCompleteBinaryTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return true;  // 空树或只有一个节点视为完全二叉树
    }

    TreeNode* root = buildTree(preorder, inorder);
    if (!root) {
        return false;  // 构建失败说明不是完全二叉树
    }

    // 遍历检查所有节点都在其父节点的右子树
    for (TreeNode* node = root; node != NULL; node = node->right) {
        if (!node->left && !node->right) {
            continue;  // 叶子节点无需检查
        }
        if (!node->right || inorder[inorder.size() - 1] != node->val) {
            return false;
        }
        inorder.pop_back();
    }

    return true;
}

// 辅助函数，根据前序和中序构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty()) return nullptr;
    TreeNode* root = new TreeNode(preorder[0]);
    auto it = find(inorder.begin(), inorder.end(), root->val);
    inorder.erase(it);  // 移除根节点对应的值
    root->left = buildTree(preorder.begin() + 1, inorder);
    root->right = buildTree(inorder, inorder.end());
    return root;
}

先序遍历和中序遍历还原二叉树，并输出先序遍历、中序遍历和后序遍历后的结果C++

先序遍历（Preorder Traversal）和中序遍历（Inorder Traversal）通常用于构建二叉树，尤其是当给定的是两个遍历序列时。下面是一个简单的C++示例，展示了如何利用这两个遍历顺序来重构二叉树并计算其相应的遍历结果：

// 假设我们有先序遍历pre[]和中序遍历in[]作为输入

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

// 通过先序遍历重建二叉树
TreeNode* buildTree(vector<int>& pre, vector<int>& in, int start, int end) {
    if (start > end)
        return nullptr;

    // 先序遍历的第一个元素是当前节点
    TreeNode* root = new TreeNode(pre[start]);

    // 找到该节点在中序遍历中的位置
    int index = find(in.begin(), in.end(), pre[start]);
    
    // 中序遍历的剩余部分用于左右子树的创建
    int leftEnd = index - 1;
    int rightStart = index + 1;

    // 分别递归地构建左子树和右子树
    root->left = buildTree(pre, in, start + 1, leftEnd);
    root->right = buildTree(pre, in, rightStart, end);

    return root;
}

// 先序遍历、中序遍历和后序遍历的实现
void printPreOrder(TreeNode* root) {
    if (root != nullptr) {
        cout << root->val << " ";
        printPreOrder(root->left);
        printPreOrder(root->right);
    }
}
void printInOrder(TreeNode* root) {
    if (root != nullptr) {
        printInOrder(root->left);
        cout << root->val << " ";
        printInOrder(root->right);
    }
}
void printPostOrder(TreeNode* root) {
    if (root != nullptr) {
        printPostOrder(root->left);
        printPostOrder(root->right);
        cout << root->val << " ";
    }
}

int main() {
    // 假设你已经有了pre和in数组，这里省略实际调用
    auto treeRoot = buildTree(pre, in, 0, pre.size() - 1);

    // 输出先序遍历、中序遍历和后序遍历的结果
    cout << "Preorder traversal: ";
    printPreOrder(treeRoot);
    cout << "\nInorder traversal: ";
    printInOrder(treeRoot);
    cout << "\nPostorder traversal: ";
    printPostOrder(treeRoot);

    return 0;
}[^1]

在这个代码中，`buildTree()`函数负责根据先序遍历和中序遍历构建二叉树，而`printPreOrder()`, `printInOrder()`, 和 `printPostOrder()` 函数则分别用于打印不同遍历方式下的结果。