题解 | #判断t1树中是否有与t2树拓扑结构完全相同的子树#

题目描述: 简单来说，这道题目就是要判断t1树中是否包含t2树。即t2是否为t1树的子树

方法一：递归
要判断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根节点相同的节点，即找到图中紫色圈的节点
        /* 三种可能，1、当前节点的左节点跟t2根节点相同
                    2、当前节点的右节点跟t2根节点相同
                    3、当前节点跟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);
    }

复杂度分析:
时间复杂度： 。其中 M,N 分别为t1，t2的节点数。因为需要先序遍历t1树，然后还需要根t2树的每个节点进行比较，所以总的时间复杂度为两者的节点的乘积。
空间复杂度： 。递归深度为N。

方法二：先序遍历
这个做法为将t1和t2通过先序遍历序列化成为一个字符串，然后再判断t1序列化后的字符串是否包含t2序列化后的字符串。
需要注意的点是：当前节点的左右节点要是为空的时候，需要加入占位符表示为空。这样才不会出现误判。

代码如下:

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)   ;
    }

复杂度分析:
时间复杂度： 。N为遍历所有节点的次数。
空间复杂度： 。字符串的长度为N。