判断两棵二叉树是否相同
哪些公司问过
答案要点
- 相同定义:结构相同且对应节点值相等
- 递归规则:都空为真,一空为假,值不等为假,否则递归比较左右子树
- 时间 O(n),空间 O(h),最坏退化为 O(n)
- 可用队列或栈成对存节点做迭代比较,避免栈溢出
- 变体:对称二叉树镜像比较,子树判断对每个节点做相同判断
易错点
- 只判断值相等,漏了一空一非空的情况导致空指针访问
- 只比较某一种遍历序列,忽略结构差异
- 把相同树和对称树的递归比较对象搞混
面试官常见追问
- 判断一棵树是不是另一棵的子树怎么做?
- 能不能只比较两棵树的中序遍历结果?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场