判断t2树是否为t1树的子树

（牛客网—牛客题霸算法篇—NC98）

题目描述

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

思路

Java实现
递归
要判断t2是否为t1的子树，那么就先在t1中找到t2的根节点，然后再进行遍历。
判断从当前节点的左右子树相不相同，如果一旦出现不同，那么立即返回false。
如果t2遍历完节点，t1也遍历完节点，则证明t2为t1的子树。
如果t1先遍历完节点，t2还没遍历完节点，那么则证明t2不是t1的子树。

在isContains（）方法中使用递归方法在t1树中寻找与t2树的根节点相同的节点，有三种可能：
1、当前节点的左节点跟t2根节点相同
2、当前节点的右节点跟t2根节点相同
3、当前节点跟t2根节点相同
找到与根节点相同的之后，调用check（）方法，递归检查t1树从当前节点开始是否与t2树相同，如果t1先遍历完节点，t2还没遍历完节点，那么则证明t2不是t1的子树； 如果t2遍历完节点，t1没遍历完节点，则证明t2不是t1的子树；如果两者节点值不相同，那么证明t2不是t1的子树。

代码实现

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    public boolean check(TreeNode root1, TreeNode root2){
        if(root1==null&&root2==null)
            return true;
        if(root1==null||root2==null||root1.val!=root2.val)
            return false;
        return check(root1.left,root2.left)&&check(root1.right,root2.right);
    }
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        if(root1==null)
            return false;
        return isContains(root1.left,root2)||isContains(root1.right,root2)||check(root1,root2);
    }
}