原题
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3 / \ 4 5 / \ 1 2
给定的树 t:
4 / \ 1 2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s:
3 / \ 4 5 / \ 1 2 / 0
给定的树 t:
4 / \ 1 2
返回 false。
解法
思想
参考leetcode100-相同的树的做法,递归判断t和s中的子树是否相同。
代码
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return t == null || isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
return (p==null && q==null) || (q!=null && p!= null && p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right));
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode572-%e5%8f%a6%e4%b8%80%e4%b8%aa%e6%a0%91%e7%9a%84%e5%ad%90%e6%a0%91/