小编给大家分享一下LeetCode如何实现树的子结构，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构， 即 A 中有出现和 B 相同的结构和节点值。
例如: 给定的树 A:
3 / \ 4 5 / \ 1 2
给定的树 B：
4 / 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
0 <= 节点个数 <= 10000
A = [1,2,3], B = [3,1]
false
A = [3,4,5,1,2], B = [4,1]
true
计算
安全
数据库
网络和加速
企业服务
O(MN)O(MN)O(M)O(M) 递归栈空间, match 递归调用使用
O(min(M, N)) 递归栈空间, 所以整体空间复杂度为
O(M)class Solution: def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: if not A or not B: # 根据题意, B如果是空树一定不满足条件, 而A是空树的话B更不可能是其子结构了 return False def match(a, b): if not b: # 因为A的子树部分可以有部分节点是B没有的, 所以如果当前b节点是空的话是满足条件的情况, 直接返回true return True if not a: # 此时b节点还有值, 但a节点是空了, B不可能是A的子结构 return False # 既要当前a和b的值相等, 同时各自左右子树部分也要匹配 return a.val == b.val and match(a.left, b.left) and match( a.right, b.right) # B是A的子结构的充要条件: 要么当前A和B匹配, 要么A的左右子节点和B匹配 return match(A, B) or self.isSubStructure( A.left, B) or self.isSubStructure(A.right, B)以上是“LeetCode如何实现树的子结构”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4633874/blog/4546054
