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

题意整理：
给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。即在root1树中，是否能找到与root2树相同结构的子树。
解法一：
思路：
这道题就是判断root2是否是root1的子树，第一种解法采用递归的方法，遍历root1的所有节点，看是否有与root2结构相同的子树。
图解：
图片说明
代码：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if (root1 == NULL) return false;//root1树为空
        if (isSame(root1, root2)) return true;//root2是root1的子树
        return isContains(root1->left, root2) || isContains(root1->right, root2);//root2是root1左子树或右子树的子树
    }
    bool isSame(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL && root2 == NULL) //root1以及root2均为空
            return true;
        if (root1 == NULL || root2 == NULL) //root1以及root2有一个为空
            return false;
        if (root1->val != root2->val) //root1与root2的值不相等
            return false;
        return isSame(root1->left, root2->left) && isSame(root1->right, root2->right);//看root1和root2的左右子树是不是都相等
    }
};

复杂度分析：
1、时间复杂度：root1有m个节点，root2有n个节点，时间复杂度应该是 $O(m×n)$ 。
2、空间复杂度：递归的本质涉及到栈的操作，空间复杂度应该是 $O(n)$ 。

解法二：
思路：
先将root1和root2序列化，然后直接比较root2是不是root1的子序列。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isContains (TreeNode root1, TreeNode root2) {
        //write code here
        String r1 = turn(root1);//将root1序列化
        String r2 = turn(root2);//将root2序列化
        return r1.contains(r2);//看r1是否包含r2序列
    }
    public String turn(TreeNode s){
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stacktree = new Stack();
        stacktree.push(s);
        while(!stacktree.isEmpty()){
           TreeNode popelem = stacktree.pop();
           if(popelem==null)
              sb.append(",#");//添加#，以处理相同的值，但不是子树的情况
           else
              sb.append(","+popelem.val);
           if(popelem!=null){
                stacktree.push(popelem.right);
                stacktree.push(popelem.left);
           }
        }
        return sb.toString();
    }
}

复杂度分析：
1、时间复杂度：线性操作，时间复杂度是 $O(n)$ 。
2、空间复杂度：涉及到栈的操作，空间复杂度是 $O(n)$ 。