树的子结构

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

    public TreeNode(int val) {
        this.val = val;

    }

}*/
public class Solution {
   public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null) return false;
        if(root1==null && root2!=null) return false;        
        boolean flag = false;
        if(root1.val==root2.val){
            flag = isSubTree(root1,root2);
        }
        if(!flag){
            flag = HasSubtree(root1.left, root2);
            if(!flag){
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }
    
    private boolean isSubTree(TreeNode root1, TreeNode root2) {
        if(root2==null) return true;
        if(root1==null && root2!=null) return false;        
        if(root1.val==root2.val){
            return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
        }
        return false;
    }
}

public class Solution {
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
		boolean result = false;
		//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
		if (root2 != null && root1 != null) {
			//如果找到了对应Tree2的根节点的点
			if(root1.val == root2.val){
				//以这个根节点为为起点判断是否包含Tree2
				result = doesTree1HaveTree2(root1,root2);
			}
			//如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
			if (!result) {
				result = HasSubtree(root1.left,root2);
			}
			
			//如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
			if (!result) {
				result = HasSubtree(root1.right,root2);
			   }
			}
		    //返回结果
		return result;
	}

	public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
		//如果Tree2已经遍历完了都能对应的上，返回true
		if (node2 == null) {
			return true;
		}
		//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
		if (node1 == null) {
			return false;
		}
		//如果其中有一个点没有对应上，返回false
    	if (node1.val != node2.val) {	
				return false;
		}
    	
    	//如果根节点对应的上，那么就分别去子节点里面匹配
    	return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }
}

class Solution {
    bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
        if (pRootB == NULL) return true;
        if (pRootA == NULL) return false;
        if (pRootB->val == pRootA->val) {
            return isSubtree(pRootA->left, pRootB->left)
                && isSubtree(pRootA->right, pRootB->right);
        } else return false;
    }
public:
    bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
    {
        if (pRootA == NULL || pRootB == NULL) return false;
        return isSubtree(pRootA, pRootB) ||
            HasSubtree(pRootA->left, pRootB) ||
            HasSubtree(pRootA->right, pRootB);
    }
};

class Solution {
public:
	bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
	{
		if (pRoot2 == NULL || pRoot1 == NULL) return false; 
		return dfs(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2)
			|| HasSubtree(pRoot1->right, pRoot2);
	}
	bool dfs(TreeNode* node, TreeNode* pRoot2) {
		if (pRoot2 == NULL) return true;
		else if (node != NULL) {
			return (node->val == pRoot2->val) && dfs(node->left, pRoot2->left)
				&& dfs(node->right, pRoot2->right);
		}
		else return false;
	}
};

public class Solution {


    public boolean HasSubtree(TreeNode tree, TreeNode sub) {
        return sub == null ? false : isSubtree(tree, sub);
    }

    private boolean isSubtree(TreeNode tree, TreeNode sub) {
        if (sub == null) return true;
        if (tree == null) return false;

        if (tree.val == sub.val) {
            boolean isSameTree = isSubtree(tree.left, sub.left) && isSubtree(tree.right, sub.right);
            if (isSameTree) return true;
        }
        return isSubtree(tree.left, sub) || isSubtree(tree.right, sub);
    }
}

    /* 改进算法，时间复杂度O（m+n）
     * 1.将root1和root2分别按先序遍历序列化。
     * 2.运用KMP算法匹配序列化结果。
     */
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	if(root2==null)
    		return false;// 空树本应是任意树的子结构，但从测试集来看，应视为false
    	if(root1==null)
    		return false;
    	char[] str = Serialize(root1).toCharArray();
    	char[] pattern = Serialize(root2).toCharArray();
    	int[] next = new int[pattern.length];
    	System.out.println(String.valueOf(str));
    	System.out.println(String.valueOf(pattern));
    	getNext(pattern,next);
		return KMP(str,pattern,next);
        
    }
	private boolean KMP(char[] str, char[] pattern, int[] next) {
		if(str==null||pattern==null)
			return false;
		if(str.length<pattern.length)
			return false;
		int i=0,j=0,len = str.length;
		while(i<len&&j<pattern.length){
			if(j==-1||str[i]==pattern[j]){
				i++;j++;
			}else{
				j = next[j];
			}
		}
		if(j==pattern.length)// 表示最后一个字符也相等，匹配成功
			return true;
		return false;
	}

	private void getNext(char[] pattern, int[] next) {
		if(pattern==null||pattern.length==0)
			return;
		int i=0,j=-1;
		next[0] = -1;
		while(i<pattern.length-1){
			if(j==-1||pattern[i]==pattern[j]){
				++i;++j;				
				if(pattern[i]==pattern[j]){
					next[i] = next[j];
				}else{
					next[i] = j;
				}
			}else{
				j = next[j];
			}
		}
	}
	public String Serialize(TreeNode root) {
		if(root==null)
			return "";
		this.buffer = new StringBuffer();
		SerializeF(root);
		int i;
		// 删除序列尾部的$
		for(i = buffer.length()-1;i>=0;i--){
			if(buffer.charAt(i)==','||buffer.charAt(i)=='$'){
				continue;
			}else
				break;
		}
		buffer.delete(i+1,buffer.length());
		return buffer.toString();
	}

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        return (root1!=null&&root2!=null)&&
            (recur(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2));
    }
    boolean recur(TreeNode A,TreeNode B){
        if(B==null)return true;//说明匹配完成 B是A的子结构
        if(A==null||A.val!=B.val)return false;//A树为空或者节点值不相等 说明不是子结构
        return recur(A.left,B.left)&&recur(A.right,B.right);
    }
}

//Javascript 描述，用flag表示函数状态。
function HasSubtree(p1, p2,flag)
{
    var f=HasSubtree;
    if(flag && !p2) return true;
    if(!p1 || !p2) return false;
    if(p1 && p2 && p1.val == p2.val) 
        return f(p1.left,p2.left,true) && f(p1.right,p2.right,true) || f(p1.left,p2)||f(p1.right,p2);
    return  f(p1.left,p2) || f(p1.right,p2);
}

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
		if(root2 == null) {
			return false;
		}
		List<TreeNode> list1 = new ArrayList<>();
		List<TreeNode> list2 = new ArrayList<>();
		preOrderTraversal(root1, list1);
		preOrderTraversal(root2, list2);
		StringBuffer sb1 = new StringBuffer();
		for (int i = 0; i < list1.size(); i++) {
			sb1.append(list1.get(i).val);
		}
		StringBuffer sb2 = new StringBuffer();
		for(int i = 0; i < list2.size(); i++) {
			sb2.append(list2.get(i).val);
		}
		return sb1.toString().indexOf(sb2.toString()) >= 0 ? true : false;
//		return !list1.contains(list2);	//是错误的做法，contains只能检测一个list钟是否包含某元素
	}
	
	public void preOrderTraversal(TreeNode root, List<TreeNode> list) {
		if(root == null) {
			return;
		}
		list.add(root);
		preOrderTraversal(root.left, list);
		preOrderTraversal(root.right, list);
	}

class Solution {
public:
//递归判断，分条件
    bool HasSubtree(TreeNode* p1, TreeNode* p2)
    {
	    if(p1==NULL||p2==NULL) return false;
    	return Hbtree(p1,p2);
	}
    bool Hbtree(TreeNode* p1, TreeNode* p2)
    {
		if(p2==NULL) return true;
        if(p1==NULL) return false;
        if(p1->val==p2->val)
        {
             if(Hbtree(p1->left,p2->left)&&Hbtree(p1->right,p2->right)) return true;
		}

        return Hbtree(p1->left,p2)||Hbtree(p1->right,p2);      
    }
};

如果最后没用debug，立的flag的错误估计我要print一天才能出来，这道题考虑的细节比较多
弄了3小时了:
         (迭代版层序遍历掌控全局)先在找到B树中的根结点在A树中的位置(注意，这个位置可能有多个，所以我这里用了
一个列表去保存这些可能的结点)，然后以B树为基准，依次遍历，看看他们的左右孩子结点的值是
不是相同的，(刚开始我直接用的地址去判断,因为python中整数是不可变的，然而忽略掉了结点
本身已经是一个地址，每个结点的地址不一样,所以用地址去判断是错误的),最后就是要注意提前
结束没有必要的遍历，节省时间，不过最坏还是有n**2,还有很大上升空间。
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        
        result1 = []
        result2 = []
        foundlst = []
        found = True
        result1.append(pRoot1)
        
        
        while result1:
            tmp = result1.pop(0)
            if tmp.val == pRoot2.val:
                foundlst.append(tmp)
            if tmp.left:
                result1.append(tmp.left)
            if tmp.right:
                result1.append(tmp.right)

        
        while foundlst:
            result1.append(foundlst.pop(0))
            result2.append(pRoot2)

            while result2:
                tmp1 = result1.pop(0)
                tmp2 = result2.pop(0)
                if tmp1.val != tmp2.val:
                    found = False
                    result1 = []
                    result2 = []
                else:
                    found = True
                    if tmp1.left:
                        result1.append(tmp1.left)
                    if tmp1.right:
                        result1.append(tmp1.right)
                    if tmp2.left:
                        result2.append(tmp2.left)
                    if tmp2.right:
                        result2.append(tmp2.right)
                        
                        
            if found == False:
                continue
            else:
                return True
        else:
            return False

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
 		
        if(root1!=null&&root2!=null){
            if(root1.val==root2.val)
                result = DoesTree1HaveTree2(root1,root2);
            if(!result)
                result = HasSubtree(root1.left,root2);
            if(!result)
                result = HasSubtree(root1.right,root2);
        }
        return result;
    }
    boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return DoesTree1HaveTree2(root1.left,root2.left)&&DoesTree1HaveTree2(root1.right,root2.right);
    }
    
}

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        // 时间复杂度O(NM)，空间复杂度O(NM)
        if (pRoot1 == nullptr || pRoot2 == nullptr) return false;
        return  dfs(pRoot1, pRoot2) || 
            HasSubtree(pRoot1->left, pRoot2) || 
            HasSubtree(pRoot1->right, pRoot2);
    }
    bool dfs(TreeNode *pRoot1, TreeNode *pRoot2) {
        if (pRoot2 == nullptr) return true;
        if (pRoot1 == nullptr) return false;
        if (pRoot1->val != pRoot2->val) return false;
        return dfs(pRoot1->left, pRoot2->left) && dfs(pRoot1->right, pRoot2->right);
    }
};

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        return (pRoot1 && pRoot2) && (recur(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2));
    }

    bool recur(TreeNode* A, TreeNode* B) {
        if (!B)
            return true;
        if (!A || A->val != B->val)
            return false;
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
};