18，树的子结构

思路比较简单。
若是一开始，就想用一个递归函数中，既能判断两个根节点相同的树是不是同一个树，又能对不同的根节点进行递归，是不太容易的。

一个函数，最好有一个功能。因此，定义一个sametree递归函数，对于传入的两个节点，判断以这两个节点为根节点的树，B是不是A的子树。

在大的hassubtree递归函数中， 用来调整两个比较的节点，传入到sametree函数中。

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    #定义一个函数，传入两个树节点，对以这两个节点为根的树判断是否为相同的树
    def sametree(self,root_A,root_B):
        #存在A树比B树大的情况，这种情况，当B树遍历到None时，A树还可能有值，不
        #过这个时候，已经知道B树这一部分是子树了，因此可以直接返回True了
        if root_B == None:
            return True
        if root_A == None:
            return False
        #若B树节点不为None，那么就要返回False
        if root_A.val != root_B.val:
            return False
        else:
            return self.sametree(root_A.left,root_B.left) and self.sametree(root_A.right,root_B.right)
        
    
    def HasSubtree(self, pRoot1, pRoot2):
        if pRoot1 == None or pRoot2 == None:
            return False
        if pRoot1.val == pRoot2.val:
            found = self.sametree(pRoot1,pRoot2)
            if found == False:
                found = self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)
        #若found的值为False，说明没有找到相同的子树，那么就继续调用此函数
        #注意此时，传入的第二个节点仍是B树的根节点
        else: 
            found = self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)
        return found