题目
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
1
2
3
4
5 3
/ \
4 5
/ \
1 2给定的树 B:
1
2
3 4
/
1返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
1
2 输入:A = [1,2,3], B = [3,1]
输出:false示例 2:
1
2 输入:A = [3,4,5,1,2], B = [4,1]
输出:true限制:
0 <= 节点个数 <= 10000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
思路很明确,前序遍历 A,因为我们首先要找到与 B 根节点匹配的 A 的子节点才能匹配。
在前序遍历的过程中,对每一个节点,将它作为可能与 B 匹配的树的根节点,与 B 进行匹配。
匹配时,首先检查根节点是否匹配,如果是,依次检查左右子树是否匹配。
一定要注意递归结束条件:
- 前序遍历的结束条件是遍历到空节点
- 匹配的结束条件是 A 与 B 至少有一个到达空节点,此时递归到最深,如果 A 是空,那么此时如果 B 也为空,说明 B 越过了叶子节点,代表一个分支匹配结束,但不一定不匹配,因此返回 true 才可以继续判断;如果 B 不为空,那么一定不匹配,返回 false;如果 A 不为空,但 B 为空,这种情况下我们一样需要返回 true。
1 | /** |
- 时间复杂度$O(MN)$,分别为两个辅助函数的递归深度,而每次递归时间复杂度$O(1)$。
- 空间复杂度$O(M)$,因为递归深度不可能超过$M$。