剑指 Offer 26. 树的子结构
本问题对应的 leetcode 原文链接:剑指 Offer 26. 树的子结构
本题对应打卡问题:【二叉树专题】剑指 Offer 26. 树的子结构
问题描述
输入两棵二叉树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
限制:
0 <= 节点个数 <= 100000
解题思路
视频讲解直达: 本题视频讲解
代码实现
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
if(isSubTree(A, B)){
return true;
}
if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
return true;
}
return false;
}
public boolean isSubTree(TreeNode Ta, TreeNode Tb){
if(Tb == null){
return true;
}
if(Ta == null){
return false;
}
if(Ta.val != Tb.val){
return false;
}
return isSubTree(Ta.left, Tb.left) &&
isSubTree(Ta.right, Tb.right);
}
}
假设树A的节点个数为 n, 树B为k,则
时间复杂度:isSubTree函数的时间复杂度为 O(k),所以时间复杂度为 O(n*k)。
空间复杂度:空间复杂度为树 A 的高度。
评论(1)
omn
om
若B是A的字结构,则子结构的根节点可能是树A的任意一个节点,所以首先先序遍历树A中的每个节点 a,判断A种以 a 为根节点的子树是否包含树B