剑指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：从匹配的节点开始，递归比较两棵树的对应节点是否相同
  

1. public class Solution {
2.     public boolean isSubStructure(TreeNode A, TreeNode B) {
3.         // 空树不是任何树的子结构
4.         if (A == null || B == null) return false;
5.         
6.         // 三种情况满足一种即可：
7.         // 1. B是以A为根的子结构
8.         // 2. B是A左子树的子结构
9.         // 3. B是A右子树的子结构
10.         return hasSubtree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
11.     }
12.    
13.     // 判断B是否是A的子结构（从当前节点开始）
14.     private boolean hasSubtree(TreeNode A, TreeNode B) {
15.         // B已经遍历完，说明匹配成功
16.         if (B == null) return true;
17.         // A遍历完但B还有节点，或节点值不匹配
18.         if (A == null || A.val != B.val) return false;
19.         // 递归比较左右子树
20.         return hasSubtree(A.left, B.left) && hasSubtree(A.right, B.right);
21.     }
22. }

复制代码

• 时间复杂度​：O(mn)，m和n分别是树A和树B的节点数
  
• ​空间复杂度​：O(m)，递归栈的深度最大为树A的高度
  

迭代+递归混合法

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

1. public class Solution {
2.     public boolean isSubStructure(TreeNode A, TreeNode B) {
3.         if (A == null || B == null) return false;
4.         
5.         Stack<TreeNode> stack = new Stack<>();
6.         stack.push(A);
7.         
8.         while (!stack.isEmpty()) {
9.             TreeNode node = stack.pop();
10.             // 找到匹配的根节点，开始递归比较
11.             if (node.val == B.val && compareTrees(node, B)) {
12.                 return true;
13.             }
14.             if (node.right != null) stack.push(node.right);
15.             if (node.left != null) stack.push(node.left);
16.         }
17.         
18.         return false;
19.     }
20.    
21.     private boolean compareTrees(TreeNode A, TreeNode B) {
22.         if (B == null) return true;
23.         if (A == null || A.val != B.val) return false;
24.         return compareTrees(A.left, B.left) && compareTrees(A.right, B.right);
25.     }
26. }

复制代码

• 时间复杂度​：O(mn)
  
• ​空间复杂度​：O(m)，栈的空间消耗
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！