基于中序与前序遍历序列构建二叉树及技术问询

1. 如何根据给定中序与前序序列构建二叉树？ #

以题目给出的序列为例：

• 中序遍历：{4, 2, 5, 1, 6, 3}
• 前序遍历：{1, 2, 4, 5, 3, 6}

构建步骤如下：

1. 确定根节点：前序遍历的第一个元素就是整棵树的根节点，即1。
2. 划分左右子树：在中序遍历中找到根节点1的位置（索引为3），其左侧{4,2,5}是左子树的中序序列，右侧{6,3}是右子树的中序序列。
3. 确定子树的前序序列：左子树的节点数量是3个，因此前序中根节点1之后的前3个元素{2,4,5}就是左子树的前序序列；剩下的{3,6}是右子树的前序序列。
4. 递归构建子树：对左子树（中序{4,2,5}、前序{2,4,5}）和右子树（中序{6,3}、前序{3,6}）重复上述步骤：
   • 左子树：前序首元素2是根，中序中2的左侧是{4}，右侧是{5}，对应前序中2之后的1个元素{4}是左子树，再后面的1个元素{5}是右子树。
   • 右子树：前序首元素3是根，中序中3的左侧是{6}，右侧为空，对应前序中3之后的1个元素{6}是左子树。

最终构建出的二叉树结构为：

1
      /   \
     2     3
    / \   /
   4   5 6

2. 为何中序+前序/后序可构建唯一二叉树，前序+后序不行？ #

核心原因是中序遍历能明确区分根节点的左右子树范围：

• 前序遍历遵循「根→左→右」，后序遵循「左→右→根」，两者都能快速定位根节点，但无法直接确定左右子树的边界。而中序遍历的「左→根→右」结构，一旦找到根节点，其左右两侧就是明确的左右子树节点集合，结合前/后序的根位置，就能唯一确定子树的遍历序列，递归构建出唯一的树。
• 前序+后序组合无法区分左右子树的边界，会出现多解情况。比如：
  • 前序序列：{1,2}，后序序列：{2,1}
  • 既可以是1的左孩子为2，也可以是1的右孩子为2，两种树结构都满足这两个遍历序列，因此无法唯一确定。

3. 中序与前序构建二叉树的算法及C++实现 #

算法步骤 #

1. 若当前遍历序列为空（起始索引大于结束索引），返回空节点。
2. 取前序序列的首元素作为当前子树的根节点。
3. 在中序序列中找到根节点的位置，计算左子树的节点数量（左子树长度 = 根索引 - 中序起始索引）。
4. 递归构建左子树：使用中序的左半段（起始到根索引-1）、前序的根后左子树长度段（起始+1到起始+左子树长度）。
5. 递归构建右子树：使用中序的右半段（根索引+1到结束）、前序的剩余段（起始+左子树长度+1到结束）。
6. 返回当前根节点。

C++实现代码 #

#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(const std::vector<int>& inorder, const std::vector<int>& traversal,
                         int in_start, int in_end, int t_start, int t_end,
                         const std::unordered_map<int, int>& inorderMap, std::string traversal_type) {
    if (in_start > in_end || t_start > t_end) {
        return nullptr;
    }

    // 获取当前根节点的值
    int root_val = traversal_type == "pre" ? traversal[t_start] : traversal[t_end];
    TreeNode* root = new TreeNode(root_val);

    // 找到根节点在中序遍历中的索引
    int root_index = inorderMap.at(root_val);
    // 计算左子树的节点数量
    int left_len = root_index - in_start;

    if (traversal_type == "pre") {
        // 前序模式：左子树用前序中t_start+1到t_start+left_len的部分
        root->left = buildTreeHelper(inorder, traversal, in_start, root_index - 1,
                                    t_start + 1, t_start + left_len, inorderMap, traversal_type);
        // 右子树用前序中剩余的部分
        root->right = buildTreeHelper(inorder, traversal, root_index + 1, in_end,
                                     t_start + left_len + 1, t_end, inorderMap, traversal_type);
    } else if (traversal_type == "post") {
        // 后序模式：先构建右子树（后序末尾是根，倒数部分是右子树）
        root->right = buildTreeHelper(inorder, traversal, root_index + 1, in_end,
                                     t_start, t_start + left_len, inorderMap, traversal_type);
        // 再构建左子树
        root->left = buildTreeHelper(inorder, traversal, in_start, root_index - 1,
                                    t_start + left_len + 1, t_end - 1, inorderMap, traversal_type);
    }

    return root;
}

// 对外暴露的构建函数
TreeNode* buildTree(const std::vector<int>& inorder, const std::vector<int>& traversal, std::string traversal_type) {
    // 构建中序值到索引的映射，避免每次查找都遍历
    std::unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); ++i) {
        inorderMap[inorder[i]] = i;
    }
    return buildTreeHelper(inorder, traversal, 0, inorder.size()-1, 0, traversal.size()-1, inorderMap, traversal_type);
}

// 测试函数：中序遍历输出，验证构建结果
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    std::cout << root->val << " ";
    printInorder(root->right);
}

int main() {
    // 题目给定的遍历序列
    std::vector<int> inorder = {4, 2, 5, 1, 6, 3};
    std::vector<int> preorder = {1, 2, 4, 5, 3, 6};

    // 构建二叉树
    TreeNode* root = buildTree(inorder, preorder, "pre");

    // 输出中序遍历验证
    std::cout << "构建后的二叉树中序遍历结果：";
    printInorder(root);
    std::cout << std::endl;

    // 释放内存（实际项目中需注意内存管理）
    // 此处省略内存释放代码，可自行实现递归销毁函数

    return 0;
}

代码说明 #

• 用unordered_map存储中序序列的值与索引的映射，将查找根节点位置的时间复杂度从O(n)降到O(1)。
• 辅助函数buildTreeHelper通过索引范围划分子树序列，避免频繁截取子数组，提升效率。
• 支持前序和后序两种模式与中序组合构建，对应代码中traversal_type的分支处理。

内容的提问来源于stack exchange，提问作者kikall