《剑指offer》—— 17. 树的子结构（Java）
推荐
完整《剑指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);
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
