572. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

3
/
4 5
/
1 2
给定的树 t：

4
/
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subtree-of-another-tree

public class SubtreeofAnotherTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    //子树必须从叶结点开始，中间某个部分不是子树，转换一下思路，从某个节点s开始，
    //跟t的所有结构都一样，那么问题就转换成判断两棵树是否相同
    public boolean isSubtree(TreeNode s, TreeNode t) {
/*        if(s == null && t == null) {  //和27-34行效果相同
            return true;
        }
        if(s == null) {
            return false;
        }
        if(t == null) {
            return true;
        }
        boolean result = false;
        if(s.val == t.val) {
            result = isSameTree(s, t);
        }*/
        
        if(t == null) {
            return true;
        }
        if(s == null) {
            return false;
        }
        boolean result = false;
        result = isSameTree(s, t);  //判断是不是同一树
        
        
        if(!result) {  //如果不是，则判断s的左子树是否和t相同
            result = isSubtree(s.left, t);
        }
        if(!result) {  //如果仍不是，则判断s的右子树是否和t相同
            result = isSubtree(s.right, t);
        }
        return result;
    }
    
    //判断两棵树是否是一样
    public static boolean isSameTree(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {  //最后都同时为null则该节点为叶节点，且相同
            return true;
        }
        if(root1 == null || root2 == null) { //其中一个不为null，说明两节点的子节点不同，该节点也就不同
            return false;
        }
        if(root1.val != root2.val) {  //值不同两节点也不同
            return false;
        }
        return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
    }
}