【C++】每日一题 105 从前序和中序序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

#include <iostream>
#include <vector>
#include <unordered_map>

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

TreeNode* buildTreeHelper(std::vector<int>& preorder, std::vector<int>& inorder, int preStart, int inStart, int inEnd, std::unordered_map<int, int>& indexMap) {
    if (preStart >= preorder.size() || inStart > inEnd) {
        return nullptr;
    }

    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);

    int inIndex = indexMap[rootVal];

    root->left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, inIndex - 1, indexMap);
    root->right = buildTreeHelper(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd, indexMap);

    return root;
}

TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) {
        return nullptr;
    }

    std::unordered_map<int, int> indexMap;
    for (int i = 0; i < inorder.size(); ++i) {
        indexMap[inorder[i]] = i;
    }

    return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1, indexMap);
}

void printInorder(TreeNode* root) {
    if (root) {
        printInorder(root->left);
        std::cout << root->val << " ";
        printInorder(root->right);
    }
}

int main() {
    std::vector<int> preorder = {3, 9, 20, 15, 7};
    std::vector<int> inorder = {9, 3, 15, 20, 7};

    TreeNode* root = buildTree(preorder, inorder);

    std::cout << "Inorder traversal of the constructed tree: ";
    printInorder(root);
    std::cout << std::endl;

    return 0;
}

当给定先序遍历 preorder 和中序遍历 inorder 数组时，我们可以通过递归的方式构造二叉树。详细的构造过程如下：

确定根节点：

先序遍历的第一个元素必定是当前子树的根节点的值。
在中序遍历数组中找到根节点的位置，根节点左边的元素属于左子树，右边的元素属于右子树。

递归构造左子树：

根据中序遍历的结果，左子树的元素位于根节点左边，右子树的元素位于根节点右边。
在先序遍历中，左子树的元素紧随在根节点后面，因此可以使用递归构造出左子树。

递归构造右子树：

同理，右子树的构造也可以通过递归完成。
重复以上步骤：

对左子树和右子树分别进行递归构造，直到所有节点都被处理。
在实现代码中，我们使用 buildTreeHelper 函数来辅助递归构造二叉树。该函数接受先序遍历数组、中序遍历数组、当前子树在先序遍历中的起始位置、当前子树在中序遍历中的起始位置和结束位置以及存储中序遍历元素索引的哈希表。根据这些参数，函数递归构造二叉树并返回根节点。

最后，在 main 函数中，调用 buildTree 函数传入先序遍历数组和中序遍历数组，构造出二叉树的根节点，并输出该二叉树的中序遍历结果作为验证。整个构造过程就是根据先序遍历和中序遍历的特性，逐步确定每个节点的位置，然后递归构造左右子树，最终构建整棵二叉树。