方法一

思路

题目要求判断树t1是否有与t2拓扑结构完全相同的子树，即判断t2是否为t1的一个子树。最容易想到的方法就比较t1与t2的每一个节点。

具体步骤

• 首先判断树t1是否为空，为空则直接返回false；

• 比较t1的根节点与t2的根节点，不同则比较t1的左节点与t2的根节点以及t1的右节点与t2的根节点，如此循环往复;

• 若是能找到完全相同的结构，则返回true。
  

• 大致步骤如上所示，这里采用的是递归来实现遍历查找的，具体代码如下：

  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
     // t1为空，返回false
     if (root1 == null){
         return false;
     }
     // 递归调用子问题：1.（t1的左子树，t2），2.(t1的右子树，t2)，3.(t1，t2)
     return isContains(root1.left,root2) ||
         isContains(root1.right,root2)||
         isSub(root1,root2);
  }
  // 判断t2是否为t1的子树
  private boolean isSub(TreeNode root1,TreeNode root2){
     if (root1 == null && root2 == null){
         return true;
     }
     if (root1 == null || root2 == null || root1.val != root2.val){
         return false;
     }
     // 根节点相同，比较两棵树的子节点
     return isSub(root1.left,root2.left) && 
         isSub(root1.right,root2.right);
  }
  }

• 时间复杂度：，由于最坏的情况需要遍历两棵树，所以为；

• 空间复杂度：，空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于结点数。。

  方法二

  思路

  Java中有判断一个字符串是否包含另一个字符串的函数，String.indexOf(),故可以考虑将两棵树转换成字符串序列，再由String.indexOf（）进行判断。

  具体步骤

• 采用后序遍历将t1以及t2转换成字符串s1,s2.

• 基于s1.indexOf(s2)判断t1中是否包含子树t2

• 代码如下：

  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) {
     //对二叉树 ，进行后序遍历
     String s1 = PostOrderTraverse(root1);
     String s2 = PostOrderTraverse(root2);
     return s1.indexOf(s2) > -1;
  }
  
  // 后序遍历
  private String PostOrderTraverse(TreeNode root) {
     StringBuilder sb = new StringBuilder();
     if (root == null) {
         return sb.toString();
     }
     sb.append(PostOrderTraverse(root.left)).
         append(",").
         append(PostOrderTraverse(root.right)).
         append(",").
         append(root.val);
     return sb.toString();
  }
  }

• 时间复杂度：，遍历需要O(N)，而jdk的indexOf的时间复杂度为，故时间复杂度为；

• 空间复杂度：,空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于结点数。