推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。
（ps：我们约定空树不是任意一个树的子结构）

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        
    }
}

思路：

大概就是

判断树A 是否和树B 一样，一样的话返回true，不一样的话执行下一步；
判断树A的左子树和树A的右子树是否和树B 一样，一样的话返回true，不一样的话执行下一步；
判断树A的左子树的左子树、树A的左子树的右子树和树A的右子树的左子树、树A的右子树的右子树是否和树B 一样，一样的话返回true，不一样的话执行下一步；
... ... （就是重复判断树A的子子孙孙树中是否有和树B 一样的结构。）

那我们只需写个判断方法，递归判断即可。

实现：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
   public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    //先判断tree1和tree2是否为0，为0则直接返回false
    if (root1 == null || root2 == null)
        return false;
    //判断tree1是否和tree2一样
    //再判断tree1的左子树和右子树是否和tree2
    //再判断tree1的左子树的左右子树 和 右子树的左右子树 是否和tree2 一样
    //如此往复递归下去，直到找到结果
    return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}

private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
    //如果tree2已经遍历完了，且能对应上，则返回true
    if (root2 == null)
        return true;
    //如果tree2还没有遍历完，而tree1已经遍历完了，则说明不存在，返回false
    if (root1 == null)
        return false;
    //如果tree1的节点和tree2的节点不对应，则返回false
    if (root1.val != root2.val)
        return false;
    用同样的方法递归判断tree1和tree2的下一个左节点，和下一个右节点
    return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注：如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！

《剑指offer》—— 17. 树的子结构（Java）

推荐

题目描述