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 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 q1 = new LinkedList(); LinkedList 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); }}*/