树的子结构

题目来源：牛客网--树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

先遍历root1，如果有节点和root2的根节点值相同，就从此节点开始对两棵树进行比对，如果相同返回true，不同继续遍历，直到root1完全遍历。因为root1可能有多个节点和root2 的根节点值相同。

提交代码

// 查找root1中，与root2根节点相同的节点
static boolean hasSubtree(TreeNode root1,TreeNode root2) {
    // 判断root2是否是空树
    if (root2 == null){
        return false;
    }
    // 判断节点是否为空
    if (root1 == null){
        return false;
    }
    // root1 目前节点 等于 root2 的根节点
    if (root1.val == root2.val) {
        // 判断root2 是 root1的子树才返回,否则继续遍历
        if(sameTree(root1, root2)){
            return true;
        }
    }
    // 递归遍历左子树
    boolean flag1 = hasSubtree(root1.left, root2);
    // 递归遍历右子树
    boolean flag2 = hasSubtree(root1.right, root2);
    
    // root1 的左子树 或 右子树,有一个包含 root2 就返回true
    return flag1 || flag2;
}

// 从root1当前节点, 判断root2 是否是root1 的子节点
static boolean sameTree(TreeNode root1,TreeNode root2) {
    // 当把 root2 的左子树或者右子树遍历完,返回true
    if (root2 == null){
        return true;
    }
    // root1 提前遍历完，就表示root2 不是root1 当前节点下的子树
    if (root1 == null){
        return false;
    }
    if (root1.val != root2.val) {
        return false;
    }
    // 递归遍历左子树
    boolean flag1 = sameTree(root1.left, root2.left);
    // 递归遍历右子树
    boolean flag2 = sameTree(root1.right, root2.right);
    
    // 只有左右子树都为true，才能判断root2 是root1 的子树
    return flag1 && flag2;
}

本地测试代码

package two;

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * @author jiayanzhao
 * @creation
 */
public class HasSubTree {
    public static void main(String[] args) {
        // 随便扯俩树， 还应该补上 root1 中有多个节点等于 root2 的根节点
        TreeNode one = new TreeNode(10);
        one.left = new TreeNode(1);
        one.right = new TreeNode(2);
        
        TreeNode two = new TreeNode(10);
        two.left = new TreeNode(1);
        two.right = new TreeNode(2);

        System.out.println(hasSubtree(one, two));
    }

    // 查找root1中，与root2根节点相同的节点
    static boolean hasSubtree(TreeNode root1,TreeNode root2) {
        // 判断root2是否是空树
        if (root2 == null){
            return false;
        }
        // 判断节点是否为空
        if (root1 == null){
            return false;
        }
        // root1 目前节点 等于 root2 的根节点
        if (root1.val == root2.val) {
            // 判断root2 是 root1的子树才返回,否则继续遍历
            if(sameTree(root1, root2)){
                return true;
            }
        }
        // 递归遍历左子树
        boolean flag1 = hasSubtree(root1.left, root2);
        // 递归遍历右子树
        boolean flag2 = hasSubtree(root1.right, root2);
        
        // root1 的左子树 或 右子树,有一个包含 root2 就返回true
        return flag1 || flag2;
    }

    // 从root1当前节点, 判断root2 是否是root1 的子节点
    static boolean sameTree(TreeNode root1,TreeNode root2) {
        // 当把 root2 的左子树或者右子树遍历完,返回true
        if (root2 == null){
            return true;
        }
        // root1 提前遍历完，就表示root2 不是root1 当前节点下的子树
        if (root1 == null){
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        // 递归遍历左子树
        boolean flag1 = sameTree(root1.left, root2.left);
        // 递归遍历右子树
        boolean flag2 = sameTree(root1.right, root2.right);
        
        // 只有左右子树都为true，才能判断root2 是root1 的子树
        return flag1 && flag2;
    }
}


class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;

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

     }
}