剑指offer-17、树的⼦结构
题⽬描述输⼊两棵⼆叉树A ， B ，判断B 是不是A 的⼦结构。（ps：我们约定空树不是任意⼀个树的⼦结构）
假如给定A 为{8,8,7,9,2,#,#,#,#,4,7} ， B 为{8,9,2} ， 2 个树的结构如下，可以看出B是A 的⼦结构:
思路及解答
双重递归法（标准解法）
使用两个递归函数：
[*]isSubStructure：遍历树A的每个节点，寻找与树B根节点值相同的节点
[*]recur：从匹配的节点开始，递归比较两棵树的对应节点是否相同
public class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 空树不是任何树的子结构
if (A == null || B == null) return false;
// 三种情况满足一种即可：
// 1. B是以A为根的子结构
// 2. B是A左子树的子结构
// 3. B是A右子树的子结构
return hasSubtree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
// 判断B是否是A的子结构（从当前节点开始）
private boolean hasSubtree(TreeNode A, TreeNode B) {
// B已经遍历完，说明匹配成功
if (B == null) return true;
// A遍历完但B还有节点，或节点值不匹配
if (A == null || A.val != B.val) return false;
// 递归比较左右子树
return hasSubtree(A.left, B.left) && hasSubtree(A.right, B.right);
}
}
[*]时间复杂度：O(mn)，m和n分别是树A和树B的节点数
[*]空间复杂度：O(m)，递归栈的深度最大为树A的高度
迭代+递归混合法
[*]使用迭代法（栈或队列）遍历树A
[*]当找到与树B根节点值相同的节点时，切换到递归比较
[*]结合了迭代和递归的优点
public class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) return false;
Stack<TreeNode> stack = new Stack<>();
stack.push(A);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 找到匹配的根节点，开始递归比较
if (node.val == B.val && compareTrees(node, B)) {
return true;
}
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return false;
}
private boolean compareTrees(TreeNode A, TreeNode B) {
if (B == null) return true;
if (A == null || A.val != B.val) return false;
return compareTrees(A.left, B.left) && compareTrees(A.right, B.right);
}
}
[*]时间复杂度：O(mn)
[*]空间复杂度：O(m)，栈的空间消耗
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]