二叉树考古学：从前中序序列还原树结构的忍者秘术

现实映射：破碎陶罐的复原

考古学家发现了一个破碎的陶罐，残片上记录着两种特殊符号序列：

• 前序符号：按"中心→左→右"顺序记录的图案
• 中序符号：按"左→中心→右"顺序记录的图案

现在需要根据这两种符号序列，复原陶罐原本的立体结构。这正是我们今天要解决的算法难题！

问题描述

LeetCode第105题要求：给定两个整数数组preorder和inorder，其中preorder是二叉树的前序遍历，inorder是同一棵树的中序遍历，请构造并返回这颗二叉树。

示例：

输入：
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

输出：
    3
   / \
  9  20
    /  \
   15   7

直觉解法：递归分治

就像考古学家分层剥离土层，我们可以用分治策略层层解析：

1. 定位根节点：前序数组的第一个元素是根节点
2. 划分左右区间：在中序数组中找到根节点，左边是左子树，右边是右子树
3. 递归构建：根据区间长度切割前序数组，递归构建左右子树

Java实现

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length-1, 
                    inorder, 0, inorder.length-1);
    }

    private TreeNode build(int[] pre, int preStart, int preEnd,
                          int[] in, int inStart, int inEnd) {
        if (preStart > preEnd) return null;

        // 定位根节点在中序数组的位置
        int rootVal = pre[preStart];
        int rootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        // 计算左子树长度
        int leftSize = rootIndex - inStart;
        
        TreeNode root = new TreeNode(rootVal);
        root.left = build(pre, preStart+1, preStart+leftSize,
                         in, inStart, rootIndex-1);
        root.right = build(pre, preStart+leftSize+1, preEnd,
                          in, rootIndex+1, inEnd);
        return root;
    }
}

复杂度分析
时间复杂度：O(n²)（每次递归需要线性查找根节点）
空间复杂度：O(n)（递归栈深度）

忍者解法：哈希表预处理的奥义

真正的考古大师会提前制作符号索引表！通过预处理中序数组，我们可以将时间复杂度优化到线性级别。

核心优化点

1. 哈希映射：预先存储中序数组的值与索引的对应关系
2. 全局指针：使用指针跟踪前序数组的构建进度

关键步骤演示（以示例说明）

中序哈希表：{9:0, 3:1, 15:2, 20:3, 7:4}

构建过程：
1. pre[0]=3 作为根，中序中索引1
   → 左子树区间[0,0]，右子树区间[2,4]
2. 递归构建左子树：pre[1]=9
   → 中序索引0，无左右子树
3. 递归构建右子树：pre[2]=20
   → 中序索引3，分割左右区间...

Java实现

class Solution {
    private Map<Integer, Integer> inMap = new HashMap<>();
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构建哈希映射
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length-1);
    }

    private TreeNode build(int[] pre, int left, int right) {
        if (left > right) return null;

        int rootVal = pre[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        
        // 通过哈希表直接定位
        int rootIndex = inMap.get(rootVal);
        
        root.left = build(pre, left, rootIndex-1);
        root.right = build(pre, rootIndex+1, right);
        return root;
    }
}

复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)（哈希表存储）

解法对比

方法	时间复杂度	空间复杂度	优势
递归分治	O(n²)	O(n)	无需额外空间
哈希预处理法	O(n)	O(n)	时间效率最优

模式总结

本题体现了两个关键算法思想：

1. 分治递归：将复杂问题分解为子问题递归求解
2. 空间换时间：通过预处理建立快速查询结构

这种模式可以扩展到：

• 从中序与后序遍历构造二叉树
• 从前序与后序遍历构造二叉树（需特殊处理）
• 其他需要定位分割点的问题

考古大师心法

优秀的算法设计就像文物复原：

1. 定位锚点：快速找到关键分割点（根节点）
2. 分层解析：递归处理各个结构层次
3. 工具准备：预先建立索引工具（哈希表）提升效率

记住：当遇到需要频繁查找元素的场景时，不妨先问问自己——能否通过预处理建立快速访问的通道？

---

作者：忍者算法
公众号：忍者算法

二叉树专题精讲已整理完毕，包含20+经典题型解析及代码模板。关注公众号回复【二叉树】获取通关秘籍～