题目：输入两棵二叉树A 和B。推断B 是不是A 的子结构。

二叉树结点的定义：

/**

 * 二叉树的树结点

 */

 public static class BinaryTreeNode {

    int value;

    BinaryTreeNode left;

    BinaryTreeNode right;

}

解题思路：

要查找树A 中是否存在和树B 结构一样的子树。我们能够分成两步： 第一步在树A 中找到和B 的根结点的值一样的结点R。 第二步再推断树A 中以R 为根结点的子树是不是包括和树B 一样的结构。

代码实现

public class Test18 {

    /**

     * 二叉树的树结点

     */

    public static class BinaryTreeNode {

        int value;

        BinaryTreeNode left;

        BinaryTreeNode right;

    }

    /**

     * 输入两棵二叉树A和B，推断B是不是A的子结构。

     * 该方法是在A树中找到一个与B树的根节点相等的元素的结点。

     * 从这个相等的结点開始推断树B是不是树A的子结构，假设找到其的一个就返回，

     * 否则直到全部的结点都找完为止。

     *

     * @param root1 树A的根结点

     * @param root2 树B的根结点

     * @return true：树B是树A的子结构，false：树B是不树A的子结构

     */

    public static boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {

        // 仅仅要两个对象是同一个就返回true

        // 【注意此处与书本上的不同，书本上的没有这一步】

        if (root1 == root2) {

            return true;

        }

        // 仅仅要树B的根结点点为空就返回true

        if (root2 == null) {

            return true;

        }

        // 树B的根结点不为空。假设树A的根结点为空就返回false

        if (root1 == null) {

            return false;

        }

        // 记录匹配结果

        boolean result = false;

        // 假设结点的值相等就，调用匹配方法

        if (root1.value == root2.value) {

            result = match(root1, root2);

        }

        // 假设匹配就直接返回结果

        if (result) {

            return true;

        }

        // 假设不匹配就找树A的左子结点和右子结点进行推断

        return hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);

    }

    /**

     * 从树A根结点root1和树B根结点root2開始。一个一个元素进行推断。推断B是不是A的子结构

     *

     * @param root1 树A開始匹配的根结点

     * @param root2 树B開始匹配的根结点

     * @return 树B是树A的子结构。false：树B是不树A的子结构

     */

    public static boolean match(BinaryTreeNode root1, BinaryTreeNode root2) {

        // 仅仅要两个对象是同一个就返回true

        if (root1 == root2) {

            return true;

        }

        // 仅仅要树B的根结点点为空就返回true

        if (root2 == null) {

            return true;

        }

        // 树B的根结点不为空。假设树A的根结点为空就返回false

        if (root1 == null) {

            return false;

        }

        // 假设两个结点的值相等，则分别推断其左子结点和右子结点

        if (root1.value == root2.value) {

            return match(root1.left, root2.left) && match(root1.right, root2.right);

        }

        // 结点值不相等返回false

        return false;

    }

    public static void main(String[] args) {

        BinaryTreeNode root1 = new BinaryTreeNode();

        root1.value = 8;

        root1.right = new BinaryTreeNode();

        root1.right.value = 7;

        root1.left = new BinaryTreeNode();

        root1.left.value = 8;

        root1.left.left = new BinaryTreeNode();

        root1.left.left.value = 9;

        root1.left.right = new BinaryTreeNode();

        root1.left.right.value = 2;

        root1.left.right.left = new BinaryTreeNode();

        root1.left.right.left.left = new BinaryTreeNode();

        root1.left.right.left.left.value = 4;

        root1.left.right.left.right = new BinaryTreeNode();

        root1.left.right.left.right.value = 7;

        BinaryTreeNode root2 = new BinaryTreeNode();

        root2.value = 8;

        root2.left = new BinaryTreeNode();

        root2.left.value = 9;

        root2.right = new BinaryTreeNode();

        root2.right.value = 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));

    }

}

执行结果

输入的树：

输出结果：