对称二叉树(判断镜像)
哪些公司问过
答案要点
- 问题等价于判断左右子树是否互为镜像
- 辅助函数比较两个节点:都为空为真;一个为空为假;值不等为假
- 递归条件:左的左对应右的右,左的右对应右的左,都满足才对称
- 根为空视为对称;时间 O(n),空间 O(h)
- 迭代解法:用队列或栈,每次取两个节点比较,按镜像顺序成对加入孩子
易错点
- 只比较节点的值,不比较结构
- 镜像比较时错写成左对左
- 忘了处理两个节点都为空的情况
- 没有先判断单个节点为空,直接访问其值,空指针
面试官常见追问
- 迭代怎么写?
- 怎么判断两棵树是否相同?
- 最坏情况下的空间复杂度是多少?
- 如何翻转二叉树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场
- 二叉树的右视图7 场