题目要求判断一棵树是否包含另一棵树,广度优先遍历由于需要维护一个队列,
这个队列会依次把每一层的节点全部压入队列,在本题中本层的其他节点会造成干扰项,
所以我们使用深度优先
方法一:深度优先遍历暴力破解
class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if (t==null) return true; if (s==null) return false; // 一棵树的子树包括3种可能,(1)左子树的子树(2)右子树的子树(3)自身 (每一棵树都是其自身的子树) return isSubtree(s.left,t) || isSubtree(s.right,t) || isSameTree(s,t); } public boolean isSameTree(TreeNode s, TreeNode t) { if (s==null && t==null) return true; // s和t不全为空,但有一个为空,必然不相等 if (s==null || t==null) return false; // 此处判断2颗树是否相似,条件为左右子树都完全保持一致 if (s.val!=t.val) return false; return isSameTree(s.left,t.left) && isSameTree(s.right,t.right); } }
方法二:深度优先+KMP
我们使用深度优先遍历可以得到一个遍历序列,代表一棵树的遍历顺序,
假设s包含t,那么s的遍历序列种必然存在和t一样的字串,看到字串,我们
就想到了kmp,于是我们可以先使用DFS得到2个字符串,再使用KMP来
判断是否s是否包含字串t
(由于KMP的代码我给忘了,后面再补)