本篇文章为你整理了每日算法之树的子结构（树的子节点定义）的详细内容，包含有树的子树 树的子节点定义 树的子树有序吗 树的子节点 每日算法之树的子结构，希望能帮助你了解 每日算法之树的子结构。
输入两棵二叉树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 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);
以上就是每日算法之树的子结构（树的子节点定义）的详细内容，想要了解更多 每日算法之树的子结构的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。