剑指Offer面试题：20.树的子结构

一、题目
————————————————
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
图片说明
————————————————
二、思路
————————————————
要查找树 A 中是否存在和树 B 结构一样的子树，我们可以分成两步：第一步在树 A 中找到和 B 的根结点的值一样的结点 R，第二步再判断树 A 中以 R 为根结点的子树是不是包含和树 B 一样的结构。
————————————————
三、解决问题
————————————————
　　1.功能测试（A、B为普通二叉树；B是或者不是A树的子结构）

　　2.特殊测试（任意一个或者两个树的根结点为null；左斜树；右斜树）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-25 9:58
 */

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

public class Solution20 {

    public static void main(String[] args) {
        Solution20 demo = new Solution20();
        System.out.println("==============================");
        demo.test1();
        System.out.println("==============================");
    }
    /**
     * 输入两棵二叉树A和B，判断B是不是A的子结构。
     * 该方法是在A树中找到一个与B树的根节点相等的元素的结点，
     * 从这个相等的结点开始判断树B是不是树A的子结构，如果找到其的一个就返回，
     * 否则直到所有的结点都找完为止。
     *
     * @param root1 树A的根结点
     * @param root2 树B的根结点
     * @return true：树B是树A的子结构，false：树B是不树A的子结构
     */
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (null == root1 || null == root2){
            return false;
        }
        boolean result = false;    //用来记录判断结果
        if(root1 != null && root2 != null){    //只有两个根节点都不为null时才进行判断，否则直接返回false。
            result = doesTree1HaveTree2(root1,root2);    //调用doesTree1HaveTree2方法判断Tree2是不是Tree1的子结构
            if(!result){    //当前两个根节点的值不相等就判断root1的左子节点是否和root2节点相等
                result = doesTree1HaveTree2(root1.left,root2);
            }
            if(!result){    //root1的左子树的节点都和root2不等的情况下判断root1的右子树节点和root2是不是相等。
                result = doesTree1HaveTree2(root1.right, root2);
            }
        }
        return result;    //root1都遍历完成后返回结果。
    }
    /**
     * 从树A根结点root1和树B根结点root2开始，一个一个元素进行判断，判断B是不是A的子结构
     *
     * @param root1 树A开始匹配的根结点
     * @param root2 树B开始匹配的根结点
     * @return 树B是树A的子结构，false：树B是不树A的子结构
     */
    public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2){
        if(node2 == null){    //如果node2树先遍历完了都和node1对上，说明node2是node1的子结构返回true
            return true;
        }
        if(node1 == null){    //如果node2不为null而node1为null了说名node2不是node1的子结构，返回false
            return false;
        }
        if(node1.val != node2.val){    //只要判断过程中有一个不想等直接返回false，这里注意只是判断一个子树没有匹配的，在HasSubTree中还会判断右子树中是否存在root2结构，所以不会漏掉。
            return false;
        }
        return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
        //当前节点的值相等，判断左右两个子节点的值是不是相等，有一个不等就返回false。
    }
    //=====================测试代码=======================
    /*
     * 1.功能测试（A、B为普通二叉树；B是或者不是A树的子结构）
     * 2.特殊测试（任意一个或者两个树的根结点为null；左斜树；右斜树）
     */
    void test1() {
        TreeNode root1 = new TreeNode(8);
        root1.right = new TreeNode(7);

        root1.left = new TreeNode(8);
        root1.left.left = new TreeNode(9);
        root1.left.right = new TreeNode(2);

        root1.right.left = new TreeNode(4);
        root1.right.right = new TreeNode(7);
        TreeNode root2 = new TreeNode(8);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(2);
        System.out.println(HasSubtree(root1, root2));
        System.out.println(HasSubtree(root2, root1));
        System.out.println(HasSubtree(root1, root1.left));
        System.out.println(HasSubtree(root1, null));
        System.out.println(HasSubtree(null, root2));
        System.out.println(HasSubtree(null, null));
    }
}

图片说明
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。

剑指Offer面试题：20.树的子结构

全站热榜