面试真题

结论：给定前序遍历（根左右）和中序遍历（左根右），可唯一还原二叉树。核心要点：前序首元素为根节点；在中序中找到根位置，左侧为左子树中序，右侧为右子树中序；根据左子树节点数在前序中划分左右子树前序；递归构建左右子树。优化：用哈希表存储中序值到索引的映射，避免线性查找。时间复杂度O(n)，空间O(n)（递归栈及哈希）。示例：前序[3,9,20,15,7]，中序[9,3,15,20,7]，根3，左子树中序[9]前序[9]，右子树中序[15,20,7]前序[20,15,7]，递归即得。