题目链接

目录

1.审题

2.解题思路

3.JAVA实现

 

---

1.审题

题目说的其实已经足够详细了，不过值得注意的是：

如果两颗树是相同的，那么也算真
 

2.解题思路

题目给定两颗树，root和subRoot，判断subRoot是否是root的子树。

看上去确实有些复杂，那我们就把他拆分成简单一点的问题。

重点来咯：

第一步： 多创建一个方法 isSame，这个方法用来比较给定两颗树是否相等，相等返回真，否则假。

至于为什么，第二步会告诉你答案。^_^

第二步：在题目所给的isSubtree方法中，递归遍历root树（不断更新root，而不改变要比较的subRoot）。在遍历中，调用第一步中的isSame方法，比较两颗树是否相同。

两棵树相同，即符合题意返回真。

若不相同，一直遍历root直到root为空，则返回假

对于isSame方法如何是实现

请点链接：相同的树

链接这道题目相当于解这道题的前置条件，不过都不难的，加油┗|｀O′|┛ 嗷~~

3.JAVA实现

class Solution {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        // if(root==subRoot)return true;//相等一定只能是空的情况

        if(root==null&&subRoot!=null)return false;
        
        if(isSame(root,subRoot))return true;//当前节点开始，两颗树是一样的返回真

        boolean left=isSubtree(root.left,subRoot);
        boolean right=isSubtree(root.right,subRoot);

        //判断左右两个子树那个和subRoot相等，相等返回真，否则返回假
        return left==true?left:right;//left与子树相同，就返回Left，否则返回right，即使right也是假，那就是假
    }


    public boolean isSame(TreeNode root, TreeNode subRoot) {//判断所给的两颗树是否相同

        if(root==subRoot)return true;//两个相等只有为空的情况才是，两个数都是空树的情况
        if((root==null&&subRoot!=null)||(root!=null&&subRoot==null))return false;//结构不同返回假

        //下面判断元素是否相同
        if(root.val!=subRoot.val)return false;//两个值不相等，返回假

        //元素相等,判断判断左右子树是否相同，不相同返回假
        boolean left=isSame(root.left,subRoot.left);//判断左孩子是否相等
        boolean right=isSame(root.right,subRoot.right);//判断右孩子是否相等
        if(left==false||right==false)return false;//只要有一个是假，就返回假

        return true;
    }
}