LeetCode题解—树的子结构
LeetCode题解—树的子结构
今天继续说说树结构的算法题——树的子结构。
题目
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：输入：A = [1,2,3], B = [3,1] 输出：false
示例 2：输入：A = [3,4,5,1,2], B = [4,1] 输出：true
题解
首先，我们能肯定的是会用到遍历，因为要遍历每个节点进行比较。
那就先假设树B就是树A的子结构，而且是从根节点开始比较的，那么我们就可以进行先序遍历，从根节点开始，每个节点进行比较。
先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。
比如这样的结构：
//?A
3
/ \
4 5
/ \
1 2
//?B
3
/
4
- 首先从根节点开始比较，如果值一样，则比较左节点，右节点。
- 当树B的某个节点为null，则无须比较，直接返回。
- 当B的某个节点不为null，则比较和A的相同节点是否一样值，如果值一样则返回true，否则返回false。
根据上述逻辑，我们可以写出遍历方法：
boolean recur(TreeNode A, TreeNode B) {
//当B某个节点为null，则无需比较了，直接返回true，比较其他节点
if (B == null)
return true;
//如果相同位置的两个节点不相同，则返回false，不用再继续比较了
if (A == null || A.val != B.val)
return false;
//继续往下遍历比较
return recur(A.left, B.left) && recur(A.right, B.right);
}
这样从根节点开始比较的话，就能找出B是否为子结构。
但是，B不一定从A的根节点开始比较，比如这样的情况：
//?A
3
/ \
4 5
/ \
1 2
//?B
4
/
1
这种情况肯定就不能直接调用上述的recur方法了，因为根节点就不相同。所以我们需要去把每个节点都进行遍历比较，只要有一个节点及子节点符合条件，就代表B为子结构。
也就是每个节点都要执行上述的recur方法。
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null)
return false;
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
上述就是用到先序遍历，将A的每个节点都和B比较，然后用或的方式，只要满足一个子节点结构和B相同即可。
最后贴一下完整的代码：
//遍历A的每一个节点
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null)
return false;
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
//同时遍历A和B的相同位置节点
boolean recur(TreeNode A, TreeNode B) {
//当B某个节点为null，则无需比较了，直接返回true，比较其他节点
if (B == null)
return true;
//如果相同位置的两个节点不相同，则返回false，不用再继续比较了
if (A == null || A.val != B.val)
return false;
//继续往下遍历比较
return recur(A.left, B.left) && recur(A.right, B.right);
}
时间复杂度
假设A的节点为n，B的节点为m。isSubStructure方法遍历了树A，recur方法遍历了树B。
所以时间复杂度为O(mn)
空间复杂度
由于用到了递归，用到了堆栈帧，之前说过和最大递归深度成正比，而且A的节点数肯定大于等于B，所以空间复杂度为O(n)
感谢大家的阅读，有一起学习的小伙伴可以关注下公众号—
码上积木❤️ 每日一个知识点，建立完整体系架构。
腾讯云开发者
