树的子结构
方法一:递归的方式(利用的是深度优先遍历的思想)
public boolean isSame(TreeNode root1,TreeNode root2){
//如果root2为空,则为true(不需要考虑root1的状况)
if(root2 == null) return true;
if(root1 == null) return false;
//判断首节点的值,然后root1与root2的左子树,然后root1与root2的右子树
return root1.val == root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}
//方法一:递归的方式(利用深度优先遍历的思想)
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//判断root1和root2是否为null(空树不是任意一个树的子结构)
if(root1 == null || root2 == null) return false;
//如果首结点不相等,则依次比较左子树、右子树与root2的关系
return isSame(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right,root2);
}
方法二:层次遍历(利用的是广度优先遍历的思想)
//判断结构相同必须需要的函数
public boolean isSame(TreeNode root1,TreeNode root2){
//如果root2为空,则为true(不需要考虑root1的状况)
if(root2 == null) return true;
if(root1 == null) return false;
//判断首节点的值,然后root1与root2的左子树,然后root1与root2的右子树
return root1.val == root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}
//方法二:层次遍历的方式(利用广度优先遍历的思想)
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//判断root1和root2是否为null(空树不是任意一个树的子结构)
if(root1 == null || root2 == null){
return false;
}
//队列(先进先出的特性)
Queue<TreeNode> queue = new LinkedList<>();
//把root1放入队列中
queue.offer(root1);
//判断队列是否为null
while(!queue.isEmpty()){
//取出队列中的结点
TreeNode cur = queue.poll();
//判断该结点是否和root相等
if(isSame(cur, root2)) return true;
else{
//不相等则把该结点的不为空的左右子节点放入队列中
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
}
}
return false;
}