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);
    }
}*/