剑指offer 树的子结构

• HasSubtree函数功能：排除题目约定，直接调用HasSubtree2函数
• HasSubtree2函数功能：递归查找树root1中是否含有树root2结构
• HasSubtree3函数功能：递归判断树root1是否是树root2的延申（包含两种情况：1.root1和root2完全相同；2.root1是在root2基础上添加后代得到的）

本代码与其他题解的不同之处：

1. 代码第6行:无需判断左右子树是否含有root2，因为这已经包含在递归过程中
2. 代码第17行:添加HasSubtree3函数，功能如上
3. 代码第18行:即使当前根点值相同，也需要判断root1的左右子树是否包含root2

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        } 
        return HasSubtree2(root1, root2);
    }

    public boolean HasSubtree2(TreeNode root1,TreeNode root2) {
        if (root2 == null) {
            return true;
        } else if (root1 == null) {
            return false;
        } else if (root1.val != root2.val) {
            return HasSubtree2(root1.left, root2) || HasSubtree2(root1.right, root2);
        } else {
            return HasSubtree3(root1.left, root2.left) && HasSubtree3(root1.right, root2.right)
                || HasSubtree2(root1.left, root2) || HasSubtree2(root1.right, root2);
        }
    }

    public boolean HasSubtree3(TreeNode root1,TreeNode root2) {
        if (root2 == null) {
            return true;
        } else if (root1 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        } 
        return HasSubtree3(root1.left, root2.left) && HasSubtree3(root1.right, root2.right);
    }
}