【剑指Offer 18】树的子结构

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

代码如下：

package demo;

public class Test18 {
    /**
     * 二叉树的结点
     */
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    /**
     * 在A树中找到一个与B树的根节点相等的结点
     * @param root1 树A的根节点
     * @param root2 树B的根节点
     * @return true：找到了 false：没找到
     */
    public static boolean hasSubTree(BinaryTreeNode root1, BinaryTreeNode root2) {
        if(root1 == root2) {
            return true;
        }
        if(root2 == null) {
            return true;
        }
        if(root1 == null) {
            return false;
        }
        // 记录找到的结果
        boolean result = false;
        // 如果找到相等的结点，就进行匹配
        if(root1.value == root2.value) {
            result = match(root1, root2);
        }
        // 如果匹配成功，返回true
        if(result) {
            return true;
        }
        // 如果匹配不成功，就继续从树A的左子结点和右子结点，继续找与树B的根节点相等的结点
        return hasSubTree(root1.left, root2) || hasSubTree(root1.right, root2);
    }

    private static boolean match(BinaryTreeNode root1, BinaryTreeNode root2) {
        if(root1 == root2) {
            return true;
        }
        if(root2 == null) {
            return true;
        }
        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.value = 4;
        root1.left.right.right = new BinaryTreeNode();
        root1.left.right.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));
    }
}