【加国FB面试高频题】LeetCode 572 子树问题Python最优解来啦！附逐行解析
各位算法er看过来！
今天拆解一道加拿大Facebook面试必刷题——LeetCode 572「另一棵树的子树」
问题描述：
给定两棵二叉树root和subRoot，判断subRoot是否是root的子树（相同结构和节点值）
Python最优解（DFS + 双重递归）：
def isSubtree(root, subRoot):
if not subRoot: return True
if not root: return False
return (isSameTree(root, subRoot)
or isSubtree(root.left, subRoot)
or isSubtree(root.right, subRoot))
def isSameTree(p, q):
if not p and not q: return True
if not p or not q: return False
return (p.val == q.val
and isSameTree(p.left, q.left)
and isSameTree(p.right, q.right))
复杂度分析：
- 时间复杂度：O(m×n) → m/n分别为两棵树节点数
- 空间复杂度：O(max(m,n)) → 递归栈深度
面试技巧：
先写出isSameTree辅助函数（面试官常考基本功）
主函数递归时注意or的短路特性优化效率
可以画图说明case：root=, subRoot=
同类型拓展题：
- LeetCode 100「相同的树」
- LeetCode 101「对称二叉树」
最近在准备北美大厂面试的童鞋，欢迎在评论区交流心得呀～
下期预告：FB常考的图论BFS套路！ #算法面试 #Python刷题 #加拿大科技岗
复杂度分析也很清晰，时间复杂度和空间复杂度都有了解吗？在准备北美大厂面试的时候，可以顺便刷刷这些高频题，加油！
而subRoot是雪松时如何优化
推荐配合使用多伦多大学开发的pytutor可视化工具，面试时画图解释递归栈超有帮助！我在Waterloo面试时就靠这个拿到strong hire 
，但FB仍在扩招ML岗位。这道题在LinkedIn数据工程岗也出现过变种，建议把isSameTree单独练到肌肉记忆程度 
大家加油！
俺在温哥华面FB时候还真碰见过这题！说点实战经验：
比如加个"前序序列化+字符串匹配"的邪招儿（虽然代码变啰嗦了）
→ 
加拿大面试官贼待见可视化表达
用Python3面的话，空节点处理得显式写
）。建议搭配LeetCode 101一起刷，温哥华Amazon也常考这类树问题
：楼主这个双重递归确实是Python最优解！但加拿大面试官超爱追问优化！我分享个实战细节：
），但很多新手会忘。还有加拿大公司常用TreeNode定义可能带parent指针，要确认！
