给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。
示例1输入：
{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}
返回值：
true备注：
1≤n≤500000
方法一：递归
要判断t2是否为t1的子树，那么就先在t1中找到t2的根节点，然后再进行遍历判断从当前节点的左右子树相不相同，如果一旦出现不同，那么立即返回false。
如果t2遍历完节点，t1也遍历完节点，则证明t2为t1的子树。
如果t1先遍历完节点，t2还没遍历完节点，那么则证明t2不是t1的子树。
public boolean isContains (TreeNode root1, TreeNode root2) {
// 如果当前节点为空,那么则t2不可能为t1的子树了
if(root1 == null)
return false;
// 递归寻找t1树中跟t2根节点相同的节点，即找到图中紫色圈的节点
return isContains(root1.left,root2) || isContains(root1.right,root2)
|| check(root1,root2);
}
public boolean check(TreeNode root1,TreeNode root2){
// 如果两者的节点刚好都为空，那么返回true
if(root1 == null && root2 == null)
return true;
// 如果t1先遍历完节点，t2还没遍历完节点，那么则证明t2不是t1的子树。
// 如果t2遍历完节点，t1没遍历完节点，则证明t2不是t1的子树。
// 如果两者节点值不相同，那么证明t2不是t1的子树。
if(root1 == null || root2 == null || root1.val != root2.val)
return false;
// 递归判断，左对左，右对右
return check(root1.left,root2.left) && check(root1.right,root2.right);
}
法二：中序遍历
import java.util.*;
public class Solution {
public boolean isContains(TreeNode root1, TreeNode root2) {
// 利用先序遍历序列化两颗二叉树
String str1 = preorder(root1);
String str2 = preorder(root2);
// 然后判断str1是否包含str2即可
return str1.contains(str2);
}
// 返回先序遍历后的字符串
private String preorder(TreeNode root) {
// 节点为空 用#表示
if (root == null) {
return "#";
}
// 将先序遍历结果拼起来
return root.val + ","+ preorder(root.left) +"," + preorder(root.right) ;
}
}
明天老师又找我不知道又要为他干什么活。。。反正不可能是为我自己。。。。毕竟中期都过去了。。。
