二叉树的遍历
哪些公司问过
答案要点
- 前序:根→左→右;中序:左→根→右;后序:左→右→根;层序:按层,用队列(BFS)
- 递归写法简单;迭代用栈:中序一路向左入栈,弹出访问后转向右子树
- 层序:队列,每轮先取当前层大小,逐个处理
- 中序遍历 BST 得到有序序列;后序用于删除树、表达式求值
- 前序+中序、后序+中序可唯一还原二叉树,前序+后序不能;时间 O(n),空间 O(h)
易错点
- 写错三种顺序
- 层序遍历不记录每层的大小,无法分层
- 迭代中序忘了弹出后转向右子树
- 忘记考虑空树
面试官常见追问
- 如何不用递归和栈实现中序遍历?
- 后序遍历的迭代怎么写?
- 如何由前序和中序还原二叉树?
- 层序遍历怎么按层输出?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场
- 二叉树的右视图7 场