剑指offer JZ26 树的子结构

描述

剑指offerJZ26 树的子结构

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

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000

方法一：递归遍历判断

思路：我们可以使用两个递归遍历实现，第一个递归遍历父树root1，让root1中每一个节点都实现第二个递归，判断以当前节点为根节点的树中，是否包含子树root2。注意，root2可能在root1的中间部分，并不是只能在尾部
代码实现：

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    /**
        此方法为遍历root1的每一个节点，并且每个节点都进入confirm方法判断其是不是包含子树root2
    */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
       /**如果root2为空，则按题意返回false,如果root1为空，可能为root1整棵树为空，返回false，也可能遍历过程中走到尽头，返回false */
        if (root1 == null || root2 == null) return false;
        boolean flag1 = confirm(root1, root2);
        //向左遍历
        boolean flag2 = HasSubtree(root1.left, root2);
        //向右遍历
        boolean flag3 = HasSubtree(root1.right, root2);
        return flag1 || flag2 || flag3;

        
    }
    /**此方法便是用递归将root1和root2遍历比较，若root1中含有root2子树，则返回真 */
    public boolean confirm(TreeNode root1, TreeNode root2) {
        /**在遍历过程中，若出现root1中的节点为空，root2中的节点不为空，则说明root1中不含有root2，返回false */
        if (root1 == null && root2 != null) return false;
        /**此处包含两种情况，一是两个都为空，则返回true。二是root1不为空，root2为空，这种特殊情况需要返回true。因为上文已经过滤掉了root1为空且root2不为空的情况。可以写两个if语句直接判断两种情况，让代码更有阅读性，此处为巧妙的简写 */
        if (root1 == null || root2 == null) return true;
        if (root1.val != root2.val) return false;
        /**排除空的情况，和两个节点值不相等的情况后，就可以继续向下遍历 */
        return confirm(root1.left, root2.left) && confirm(root1.right, root2.right);
    }
}

方法二：队列实现

思路：思路与方法一大体相同，先使用队列遍历root1中的节点，若有节点的值与root2中根节点的值相同，则调用方法二，使用队列以该节点为根节点，遍历比较是否包含root2。用队列实现遍历，细节上不一样。

mport java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
 public class Solution {
    /**
        此方法通过队列遍历root1的每一个节点，并且每个节点都进入confirm方法判断其是不是包含子树root2
    */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) return false;
        Queue<TreeNode> q1 = new LinkedList<>(); 
        q1.offer(root1);
        /**遍历root1 */
        while(!q1.isEmpty()) {
            TreeNode t1 = q1.poll();
            if (t1.val == root2.val) {
                if (confirm(t1, root2)) return true;
            }
            if (t1.left != null) {
                q1.offer(t1.left);
            }
            if (t1.right != null) {
                q1.offer(t1.right);
            }
        }
        return false;

    }
    /**此方法便是用队列将root1和root2遍历比较，若root1中含有root2子树，则返回真 */
    public boolean confirm(TreeNode root1, TreeNode root2) {
       Queue<TreeNode> q1 = new LinkedList<>(); 
       Queue<TreeNode> q2 = new LinkedList<>(); 
       q1.offer(root1);
       q2.offer(root2);
       /**遍历root2比较 */
       while (!q2.isEmpty()) {
        TreeNode t1 = q1.poll();
        TreeNode t2 = q2.poll();
        /**此处判断条件与方法一有所不同，方法一需要判断四种情况，一是root1为空，root2为空，返回真。二是root1为空，root2不为空返回假。三是root1不为空， root2为空，返回真。四是root1和root2都不为空，则判断值是否相同。     
        此处因为使用队列实现的遍历，和方法一的前序遍历不同，根据下文可知，此处已经包含条件root2不为空，则不用判断情况一和情况三。 */
        if (t1 == null || t1.val != t2.val) return false;
        if (t2.left != null) {
            q2.offer(t2.left);
            q1.offer(t1.left);
        }
        if (t2.right != null) {
            q2.offer(t2.right);
            q1.offer(t1.right);
        }
       }
       return true;
    }