数据结构-剑指offer-判断树B是否是树A的子结构

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

重点：（1）递归思想的使用！递归思想在做题过程中经常出现。（2）在写遍历树的代码的时候一定要高度警惕，在每一处需要访问地址的时候都要判断这个地址是否为nullptr。

思路：判断树A中是否包含树B中的子结构，可以先比较根节点，如果根节点相同，再分别比较左节点和右节点是否相同，如果相同，则返回true，说明树B是树A的子结构。如果根节点不同，则继续遍历树A，并与B比较。

我的问题：如果A和B的根节点不同，比较A的左节点，如果A的左节点相同，比较A的左节点的左节点与B的左节点，如果A的左节点的左节点不同与B的左节点不同，则将A的左节点的左节点与B的根节点比较。那么问题来了，A子树的右节点与B进行比较的过程是怎么进行的？？？（数据结构小白啊啊啊）

针对上述问题：代码中，HasSubtree（pRoot1->left，pRoot）和HasSubtree（pRoot1->left，pRoot）是同时进行的，但具体怎么操作呢？？待解决。。。其实还是对递归和二叉树不熟悉

跟书上的代码略有不同，书上多写了一个Equal函数用于比较两个节点的值是否相等。在Equal函数中，节点中值的类型为double，在判断两个节点的值是否相等时，不能直接写pRoot1->val == pRoot2->val，因为在计算机内表示小数时（float和double型）都有误差，判断两个小数是否相等，只能判断它们之差的绝对值是不是在一个很小的范围内。如果两个数相差很小，就可以认为他们相等。

代码：

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;
        if(pRoot1 !=nullptr && pRoot2 !=nullptr)
        {
            //先比较两个二叉树的根节点
            if(pRoot1->val == pRoot2->val)
                //如果相同，以这个根节点为起点，判断Tree1是否包含Tree2
                result = DoesTree1HaveTree2(pRoot1,pRoot2);
            //如果找不到，以Tree1左子节点为起点判断是否包含Tree2
            if(!result)
                result = HasSubtree(pRoot1->left,pRoot2);
            //如果找不到，再以Tree1左子节点为起点判断是否包含Tree2
            if(!result)
                result = HasSubtree(pRoot1->right,pRoot2);
        }
        return result;
    }
    bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        //如果tree2都遍历完了且Tree1中包含该结构，则返回true
        if(pRoot2 == NULL)
            return true;
        //如果Tree1已经遍历完了仍然没有找到与Tree2相同的子结构，返回false
        if(pRoot1 == nullptr)
            return false;
        //如果根节点的值不同，直接返回false
        if(pRoot1->val != pRoot2->val)
            return false;
       return DoesTree1HaveTree2(pRoot1->left,pRoot2->left) && DoesTree1HaveTree2(pRoot1->right,pRoot2->right);
    }
};