😀前言
在算法面试中，二叉树相关的问题经常出现，其中一个经典的问题是判断一棵二叉树B是否是另一棵二叉树A的子结构。本文将深入探讨这个问题，并通过代码示例展示如何解决这一问题。

😊树的子结构

🤗题目链接

牛客网

😆问题描述

我们有两棵二叉树A和B，要求判断B是否是A的子结构。需要注意的是，题目明确规定了空树不是任何树的子结构。

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

🤔示例

• 示例1：

  输入：A = {8,8,7,9,2,#,#,#,#,4,7}，B = {8,9,2}

  输出：true

• 示例2：

  输入：A = {1,2,3,4,5}，B = {2,4}

  输出：true

• 示例3：

  输入：A = {1,2,3}，B = {3,1}

  输出：false

数据范围

• 0 ≤ A的节点个数 ≤ 10000
• 0 ≤ B的节点个数 ≤ 10000

😋解题思路

要判断B是否为A的子结构，我们可以采用递归的方法。具体步骤如下：

1. 判断当前节点是否匹配：
   • 从二叉树A的根节点开始，判断当前节点是否与树B的根节点相同。
   • 如果相同，进一步递归判断左右子树是否都匹配。
2. 递归搜索整棵树：
   • 即使当前节点与树B的根节点不匹配，我们仍需递归检查A的左右子树，继续寻找可能的匹配子结构。
3. 终止条件：
   • 如果树B的所有节点都匹配，返回true。
   • 如果树A已经遍历完且没有找到匹配，返回false。

💖Java实现

以下是该问题的Java实现代码：

public class Solution {

    // 主函数，判断B是否为A的子结构
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        // 如果A或B为空，直接返回false
        if (root1 == null || root2 == null)
            return false;

        // 检查当前节点，或递归检查左右子树
        return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    // 辅助函数，判断以root1为根的树是否包含以root2为根的子结构
    private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
        // 如果B已经遍历完，说明匹配成功
        if (root2 == null)
            return true;
        
        // 如果A先遍历完，或者当前节点不匹配，返回false
        if (root1 == null || root1.val != root2.val)
            return false;

        // 递归检查左右子树
        return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
    }
}

💖代码解析

1. HasSubtree方法：
   • 这是主函数。首先检查A和B是否为空树。如果是，返回false。否则，调用辅助函数isSubtreeWithRoot判断当前根节点是否匹配，同时递归检查A的左右子树。
2. isSubtreeWithRoot方法：
   • 这是一个递归函数，用于检查以root1为根的子树是否包含以root2为根的子结构。首先判断root2是否已经遍历完，如果是，返回true。如果root1为空或当前节点的值不相等，返回false。否则，递归检查左右子树是否匹配。

😄总结

这个问题通过递归的方式遍历二叉树，逐步检查是否存在匹配的子结构。尽管递归的方式看似复杂，但它能有效地解决类似问题。理解了这个问题的递归思路，对于二叉树相关的其他问题也会有很大帮助。

希望通过这篇文章，您对二叉树子结构的判断有了更清晰的认识和理解。