剑指offer-17、树的⼦结构

题⽬描述

输⼊两棵⼆叉树A ， B ，判断B 是不是A 的⼦结构。（ps：我们约定空树不是任意⼀个树的⼦结构）

假如给定A 为{8,8,7,9,2,#,#,#,#,4,7} ， B 为{8,9,2} ， 2 个树的结构如下，可以看出B是A 的⼦结构:

思路及解答

双重递归法（标准解法）

使用两个递归函数：

1. isSubStructure：遍历树A的每个节点，寻找与树B根节点值相同的节点
2. 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的高度

迭代+递归混合法

1. 使用迭代法（栈或队列）遍历树A
2. 当找到与树B根节点值相同的节点时，切换到递归比较
3. 结合了迭代和递归的优点

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)，栈的空间消耗