二叉树反序列化后再后序遍历
哪些公司问过
答案要点
- 确认序列化格式:先序加空节点标记可以唯一确定一棵二叉树
- 先序反序列化:按 token 顺序递归,遇 # 返回空,否则建节点再建左、右子树
- 层序格式用队列,出队节点依次读取左右孩子 token
- 后序遍历顺序为左、右、根,迭代版用栈加 prev 指针判断右子树是否已访问
- 时间、空间复杂度均为 O(n),处理空树和链状树递归过深
易错点
- 反序列化时没处理空节点标记,导致建出的树结构错误
- 用 split 后忽略末尾空串或空输入,空树时访问越界
- 树退化成链时递归深度达到 n,可能栈溢出,需要考虑迭代写法
面试官常见追问
- 只有先序和中序结果、没有空标记,能还原吗?
- 后序遍历的迭代写法还有别的吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场