判断一棵二叉树是否为另一棵的子树
哪些公司问过
答案要点
- 子树要求从某节点开始到所有叶子都完全一致,不是部分结构匹配
- isSame 递归:都空为真、一空为假、值不同为假,再比较左右子树
- 双层递归最坏 O(m×n),空间 O(h)
- 序列化加 KMP 可做到 O(m+n),序列化必须带空节点标记和分隔符
易错点
- 只比较节点值不比较结构,或在 isSame 里漏掉一空一非空的判断
- 外层递归只在根节点调用 isSame,没有继续在左右子树中查找
- 序列化不记录空节点,导致不同结构得到相同序列
面试官常见追问
- 子树和子结构有什么区别?
- T2 为空或 T1 为空怎么处理?
- 序列化时为什么值前后都要有分隔符?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场