【解题报告】lintcode245子树

题意

给出两个树，求树二是否为树一的子树 判断是否为子树的条件是从某一结点切断，剩下的部分与树二相同 例子 此时，t2是t1的子树

解法

首先，拿到t2的root，在t1中查找值相同的节点，存入数组，因为可能不止一个起点 然后再从这些节点出发，对比t2，来求是否为子树

代码

public class Solution {
         List<TreeNode> roots;
//求出发点
   public TreeNode findRoot(TreeNode node, TreeNode root) {
             if (node == null)
            return null;
        if (node.val == root.val){
            roots.add(node);
        }
             findRoot(node.left, root);
             findRoot(node.right, root);
        return null;
    }
//判断从起点开始是否相同
    public boolean findChildTree(TreeNode node,TreeNode root){
        if (node == null&&root == null)
            return true;
        if(node == null&&root != null)
            return false;
        if(node != null&&root == null)
            return false;
        if(node.val != root.val)
            return false;
        if(findChildTree(node.left,root.left)&&findChildTree(node.right,root.right))
            return true;
        else
            return false;
    }
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        // write your code here
        roots = new ArrayList<>();
        if (T2 == null)
            return true;
        TreeNode node = findRoot(T1,T2);
        for (int i = 0;i < roots.size();i++){
            if (findChildTree(roots.get(i),T2))
            {
                return true;
            }
        }
        return false;
    }

}