树是有序的吗（每日算法之树的子结构）
导读：JZ26 树的子结构 描述 输入两棵二叉树A...
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); } }*/创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！