二叉树的还原

基本概念

二叉树的还原是指根据二叉树的两种遍历序列（如前序+中序、后序+中序）唯一确定一棵二叉树的过程。由于前序（或后序）可以确定根节点，中序可以划分左、右子树，因此通过递归分治即可重建整棵树。若缺少中序序列，则无法唯一还原。

数据结构的三要素

逻辑结构
- 树形结构，每个节点最多有两个子树（左/右），节点之间存在父子关系，子树不相交。
存储结构
- 链式存储：每个节点包含数据域、左孩子指针、右孩子指针，通过指针连接成树。
- 顺序存储（数组）：按完全二叉树编号存储，但还原算法通常采用链式结构。
数据的运算
- 根据遍历序列构建二叉树（重建）。
- 树的遍历（前序、中序、后序、层序）。
- 求树高、节点数、判断是否相同等。

费曼理解

想象有一棵家族树，前序相当于先报出“爷爷”，然后报出爷爷的左支全部，再报出右支全部；中序相当于先报出左支全部，然后报出“爷爷”，最后报出右支全部。现在你拿到两份名单（前序和中序），前序的第一个名字一定是整棵树的根（爷爷），再到中序里找到爷爷的名字，左边那一堆名字就是左子树成员，右边就是右子树成员。对左右子树重复这个“找根、分左右”的过程，就能把整棵家族树重建出来。

内部实现：

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    def createTree(preorder, inorder, n):
        if n == 0:
            return None  
        idx = inorder.index(preorder[0])
        node = TreeNode(inorder[idx])
        node.left = createTree(preorder[1: idx + 1], inorder[0: idx], idx)
        node.right = createTree(preorder[idx + 1:], inorder[idx + 1:], n - idx - 1)
        return node
    return createTree(preorder, inorder, len(inorder))

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    def createTree(inorder, postorder, n):
        if n == 0:
            return None  
        idx = inorder.index(postorder[n-1])
        node = TreeNode(inorder[idx])
        node.right = createTree(inorder[idx+1:n], postorder[idx:n-1], n-idx-1)
        node.left = createTree(inorder[0:idx], postorder[0:idx], idx)
        return node
    return createTree(inorder, postorder, len(inorder))

复杂度分析：

操作	时间复杂度	空间复杂度
前序+中序还原	O(n²) （最坏，每次查找根位置需O(n)）	O(n) （递归栈 + 存储树）
后序+中序还原	O(n²) （同理）	O(n)
优化版（用哈希表存储中序下标）	O(n)	O(n) （哈希表 + 递归栈）

卡片备注：当树为链状（单支树）时，inorder.index() 每次扫描接近 n 个元素，总时间 O(n²)；空间上递归深度 O(n)，树节点 O(n)。

应用场景：

经典问题：二叉树的反序列化（如 LeetCode 105、106 题），根据遍历序列重建树，常用于网络传输或存储后的恢复。
表达式树构建：根据前缀/后缀表达式和中缀表达式还原表达式树，用于编译器或计算器。
类似思想的应用：
- LRU 缓存：HashMap + DoublyLinkedList 实现 O(1) 访问与淘汰，体现了“组合不同数据结构”的设计模式。
- Redis 有序集合：使用跳表（Skip List）代替平衡树，在概率平衡下实现 O(log n) 的查找/插入/删除，避免复杂旋转。
底层关联：微机原理中的内存布局（栈帧用于递归调用，堆用于动态分配节点）和算法复杂度分析（递归深度影响栈溢出风险）对理解还原算法的实际性能至关重要。