二叉树按先序展开为链表(LC114)
哪些公司问过
答案要点
- 原地修改:左指针置空,右指针指向先序遍历中的下一个节点
- 反向递归按右、左、根处理,用 prev 指针拼接,空间 O(h)
- 迭代法:左子树最右节点接上原右子树,左子树挪到右边,空间 O(1)
- 正向先序修改指针前必须先保存右孩子
- 时间复杂度均为 O(n)
易错点
- 修改右指针前没保存原右子树,导致子树丢失
- 忘记把左指针置空,结果不是合法链表
- 新建节点构造链表,不符合原地修改的要求
面试官常见追问
- 为什么反向递归不会丢失子树?
- 如果要展开成中序顺序的双向链表呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场