每日算法之树的子结构

JZ26 树的子结构

描述

输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构

题解1 深度遍历

思路

既然是要找到A树中是否有B树这样子树,如果是有子树肯定是要遍历这个子树和B树,将两个的节点一一比较,但是这样的子树不一定就是A树根节点开始的,所以我们还要先找到子树可能出现的位置。
既然是可能的位置,那我们可以对A树的每个节点前序递归遍历,寻找是否有这样的子树,而寻找是否有子树的时候,我们就将A树与B树同步前序遍历,依次比较节点值。
具体做法:
step 1:因为空树不是任何树的子树,所以要先判断B树是否为空树。
step 2:当A树为空节点,但是B树还有节点的时候,不为子树,但是A树不为空节点,B树为空节点时可以是子树。
step 3:每次递归比较A树从当前节点开始,是否与B树完全一致,同步前序遍历。
step 4:A树自己再前序遍历进入子节点,当作子树起点再与B树同步遍历。
step 5:以上情况任意只要有一种即可。

代码

public class Solution {
 public boolean HasSubtree(TreeNode root1, TreeNode root2) {
 if (root2 == null) return false;
 //一个节点为空 一节点不为空
 if (root1 == null) return false;
 boolean flag1 = recursion(root1, root2);
 boolean flag2 = HasSubtree(root1.left, root2);
 boolean flag3 = HasSubtree(root1.right, root2);
 return flag1 || flag2 || flag3;
 }
 // 判断是否有相等的根节点
 public boolean recursion(TreeNode root1, TreeNode root2) {
 //一个节点为空 一节点不为空
 if (root1 == null && root2 != null) return false;
 if (root1 == null || root2 == null) return true;
 if (root1.val != root2.val) return false;
 return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
 }
}

题解2 广度遍历

思路

首先对于A树层次遍历每一个节点,遇到一个与B树根节点相同的节点,我们就开始同步层次遍历比较以这个节点为根的树中是否出现了B树的全部节点。因为我们只考虑B树的所有节点是否在A树中全部出现,那我们就以B树为基,再进行一次层次遍历,A树从那个节点开始跟随B树一致进行层次遍历就行了,比较对应的每个点是否相同,或者B树是否有超出A树没有的节点。
具体做法:
step 1:先判断空树,空树不为子结构。
step 2:利用队列辅助,层次遍历第一棵树,每次检查遍历到的节点是否和第二棵树的根节点相同。
step 3:若是相同,可以以该节点为子树根节点,再次借助队列辅助,同步层次遍历这个子树与第二棵树,这个时候以第二棵树为基,只要找到第二棵树的全部节点,就算找到了子结构。

代码

package mid.JZ26树的子结构;
import java.util.LinkedList;
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) return false;
 LinkedList<TreeNode> q = new LinkedList<>();
 q.offer(root1);
 while (!q.isEmpty()) {
 TreeNode node = q.poll();
 if (node.val == root2.val) {
 if (helper(node, root2)) {
 return true;
 }
 }
 if (node.left != null) q.offer(node.left);
 if (node.right != null) q.offer(node.right);
 }
 return false;
 }
 public boolean helper(TreeNode root1, TreeNode root2) {
 LinkedList<TreeNode> q1 = new LinkedList<>();
 LinkedList<TreeNode> q2 = new LinkedList<>();
 q1.offer(root1);
 q2.offer(root2);
 while (!q2.isEmpty()) {
 TreeNode node1 = q1.poll();
 TreeNode node2 = q2.poll();
 //树1为空或者二者不相等
 if (node1 == null || node1.val != node2.val)
 return false;
 //树2还有左子树
 if (node2.left != null) {
 //子树入队
 q1.offer(node1.left);
 q2.offer(node2.left);
 }
 //树2还有右子树
 if (node2.right != null) {
 //子树入队
 q1.offer(node1.right);
 q2.offer(node2.right);
 }
 }
 return true;
 }
}
// 深度遍历查询
/*public class Solution {
 public boolean HasSubtree(TreeNode root1, TreeNode root2) {
 if (root2 == null) return false;
 //一个节点为空 一节点不为空
 if (root1 == null) return false;
 boolean flag1 = recursion(root1, root2);
 boolean flag2 = HasSubtree(root1.left, root2);
 boolean flag3 = HasSubtree(root1.right, root2);
 return flag1 || flag2 || flag3;
 }
 // 判断是否有相等的根节点
 public boolean recursion(TreeNode root1, TreeNode root2) {
 //一个节点为空 一节点不为空
 if (root1 == null && root2 != null) return false;
 if (root1 == null || root2 == null) return true;
 if (root1.val != root2.val) return false;
 return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
 }
}*/
作者:loongnuts原文地址:https://www.cnblogs.com/loongnuts/p/16947136.html

%s 个评论

要回复文章请先登录注册