另一棵的子树-力扣572题
题目
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true
示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false
解题思路
1,首先需要判断两棵树是否都空,然后是一个为空
2,其次是当两棵树都不为空,看是不是相同的树
3,最后看一棵树是否是另一棵树的子树,将一棵树的根和另一棵树根左右比较
代码实现
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
//两树都不空******
if (isSameTree(root,subRoot)) {
//相同的树
return true;
}
//子树
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public boolean isSameTree (TreeNode p, TreeNode q){
//两树都空
if (q == null && p == null) {
return true;
}
//一树空,一树不空
if (q == null || p == null) {
return false;
}
//两树都不空
if (p.val != q.val) {
return false;
}
//比较子树
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}