美团一面：给定两棵二叉树 `A` 和 `B`，判断 `B` 是否是 `A` 的子结构？

问题描述

给定两棵二叉树 A 和 B，判断 B 是否是 A 的子结构。所谓子结构是指 B 中任意节点在 A 中存在相同的结构和节点值。

例子1：

输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

思路分析

1. 基本情况：

   • 如果 A 或 B 为空，则 B 不可能是 A 的子结构，返回 false。

2. 递归检查：

   • 检查当前节点 A 和 B 是否相等。
   • 如果相等，继续递归检查 A 和 B 的左右子树是否也相等。
   • 如果不相等，继续在 A 的左子树和右子树中递归查找是否存在与 B 相同的子结构。

3. 辅助函数 playAb：

   • 用于递归比较两个节点及其子树是否相同。
   • 如果 B 为空，说明已经遍历完 B，返回 true。
   • 如果 A 为空但 B 不为空，返回 false。
   • 如果 A 和 B 的值不相等，返回 false。
   • 递归比较 A 和 B 的左右子树。

代码解释

/*** Definition for a binary tree node.*/
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {// 基本情况：如果 A 或 B 为空，则 B 不可能是 A 的子结构if (A == null || B == null) {return false;}// 检查当前节点 A 和 B 是否相等，或者在 A 的左子树或右子树中查找 Breturn playAb(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);}public boolean playAb(TreeNode A, TreeNode B) {// 如果 B 为空，说明已经遍历完 B，返回 trueif (B == null) {return true;}// 如果 A 为空但 B 不为空，返回 falseif (A == null) {return false;}// 如果 A 和 B 的值不相等，返回 falseif (A.val != B.val) {return false;}// 递归比较 A 和 B 的左右子树return playAb(A.left, B.left) && playAb(A.right, B.right);}
}

详细步骤

1. 主函数 isSubStructure：

   • 首先检查基本情况，如果 A 或 B 为空，直接返回 false。
   • 调用辅助函数 playAb 检查当前节点 A 和 B 是否相等。
   • 如果不相等，递归检查 A 的左子树和右子树中是否存在与 B 相同的子结构。

2. 辅助函数 playAb：

   • 如果 B 为空，说明已经遍历完 B，返回 true。
   • 如果 A 为空但 B 不为空，返回 false。
   • 如果 A 和 B 的值不相等，返回 false。
   • 递归比较 A 和 B 的左右子树，只有当 A 和 B 的左右子树都相等时，才返回 true。

复杂度分析

• 时间复杂度：最坏情况下，每个节点都需要进行比较，时间复杂度为 O(m * n)，其中 m 是树 A 的节点数，n 是树 B 的节点数。
• 空间复杂度：递归调用栈的空间复杂度为 O(h)，其中 h 是树的高度。

主要是利用了递归的思想，简洁且易于理解。