- 难度: 简单
- 考察: 二叉树
- 来源: https://leetcode-cn.com/problems/subtree-of-another-tree
- 题解: https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/
题目
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例1:
1 | 给定的树 s: |
示例 2:
1 | 给定的树 s: |
思路
DFS 枚举 ss 中的每一个节点,判断这个点的子树是否和 tt 相等。如何判断一个节点的子树是否和 tt 相等呢,我们又需要做一次 DFS 来检查,即让两个指针一开始先指向该节点和 tt 的根,然后「同步移动」两根指针来「同步遍历」这两棵树,判断对应位置是否相等。
关键点
- 分空二叉树
复杂度
- 时间复杂度:O(∣s∣×∣t∣)
- 空间复杂度:O(max{ds,dt})
代码
递归法
1 | /** |