翻转二叉树:交换每个节点的左右子节点(递归与迭代)
哪些公司问过
答案要点
- 对每个节点交换左右子树,空节点直接返回
- 递归:前序或后序交换均可,中序要注意避免重复翻转
- 迭代:队列层序遍历或栈遍历,逐个节点交换左右孩子
- 时间 O(n);递归空间 O(h),层序空间取决于最大层宽
- 处理空树、单节点等边界情况,深树优先考虑迭代
易错点
- 中序递归时交换后仍递归原来的右指针,同一子树被翻两次
- 交换时没有用临时变量,导致一个子树丢失
- 忽略空节点判断导致空指针访问
面试官常见追问
- 怎么判断两棵树是否互为镜像?
- 树很深时递归有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场