根据前序和中序遍历重建二叉树
哪些公司问过
答案要点
- 前序第一个元素为根,在中序中定位根,划分左右子树
- 根据左子树节点数计算前序中左右子树的区间边界
- 用哈希表存中序下标,将查找降为 O(1),总体 O(n)
- 递归传下标区间而不是复制子数组,区间为空返回空
- 要求节点值不重复;只需后序时可在递归中直接输出
易错点
- 左右子树在前序中的区间边界计算错误,导致越界或建错树
- 每次切片复制数组,时间和空间开销变大
- 没有处理空区间作为递归终止条件
- 忽略节点值必须唯一的前提
面试官常见追问
- 前序和后序能唯一确定一棵二叉树吗?
- 中序和后序怎么重建?
- 有重复值怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场